For example for n=2 coloring odd numbers red, numbers of the form 4k+2 blue and so on works.

This problem was posed in the [KoMaL][1] for n+1 prime, if I know well by Geza Kos. I verified it for all n<30, I think with a computerprogram one can easily verify it for much bigger numbers by trying certain periodic colorings.


  [1]: http://www.komal.hu/verseny/feladat.cgi?a=honap&h=201004&t=mat&l=en