2 added details of Chebotarev's density

Here is an extension of François's argument that seems to work for any $n.$ Choose a natural number $d$ so that (1) $p=nd+1$ is prime and (2) $a/b$ is not a $d$th root of unity $\mod p$ (equivalently: not an $n$th power $\mod p$) for any unequal $a,b$ from $\{1,2,\ldots,n\}$. Color a natural number $x$ by $(x')^d,$ which is an $n$th root of unity $\mod p$. By assumption (1), there are $n$ colors, and by assumption (2), $ax$ and $bx$ have different colors for $a,b$ as above. The existence of such a prime $p$ follows from the Chebotarev density theorem for the extension $K/\mathbb{Q},$ where $K$ is obtained by adjoining the $n$th roots of $1,2,\ldots,n.$ We require that $p$ split completely in $K_n=\mathbb{Q}(\zeta_n)$, which is equivalent to (1), and that each factor remain prime not split completely in every extension $K_n(\sqrt[n]{a/b})/K_n$ with $a,b$ as above, which implies is equivalent to (2).

EDIT Judging by some comments, I am hesitant to say that it's a complete proof because my far from the only one whose algebraic number theory is out of shape, so let me give a few details about Chebotarev's density. The extension $K/K_n$ is the composite of Kummer's extensions $K_n(\sqrt[n]{q})/K_n$ corresponding to primes $q\leq n.$ The Galois group $G=\operatorname{Gal}(K/\mathbb{Q})$ is the semidirect product

$$1\to(\mathbb{Z}_n)^r\to G\to (\mathbb{Z}_n)^{*}\to 1,$$

where $r$ is the number of such primes. The requirement (1) that $p$ split in $K_n$, i.e. that $\mathbb{Z}/p\mathbb{Z}$ contains the $n$th roots of unity (which happens iff $p\equiv 1 (\mod n)$) means that the Frobenius element $Fr_p$ projects to 1, i.e. it lies in the subgroup $N=(\mathbb{Z}_n)^r.$ Assuming (1), the requirement that $a/b=q_1^{k_1}\ldots q_r^{k_r}$ not be $n$th power $\mod p$ translates into "$Fr_p$ avoids the subgroup $N_{k}$ of $N$," where

$$N_k = \{(a_1,\ldots,a_r): k_1 a_1 + \ldots +k_r a_r=0\}.$$

The Chebotarev density theorem says that for any conjugacy class $C$ of $G$, the primes $p$ such that $Fr_p\in C$ have density $|C|/|G|.$ In particular, such $p$ exists!A slight unusual feature of our situation is that we apply Chebotarev's theorem in the case of a non-abelian extension. Finally, we need to see that the union of various $N_k$s is not all of $N$. I have a truly marvelous proof of this proposition, but the margins of MO are too thin to contain it.

1

Here is an extension of François's argument that seems to work for any $n.$ Choose a natural number $d$ so that (1) $p=nd+1$ is prime and (2) $a/b$ is not a $d$th root of unity $\mod p$ (equivalently: not an $n$th power $\mod p$) for any unequal $a,b$ from $\{1,2,\ldots,n\}$. Color a natural number $x$ by $(x')^d,$ which is an $n$th root of unity $\mod p$. By assumption (1), there are $n$ colors, and by assumption (2), $ax$ and $bx$ have different colors for $a,b$ as above. The existence of such a prime $p$ follows from the Chebotarev density theorem for the extension $K/\mathbb{Q},$ where $K$ is obtained by adjoining the $n$th roots of $1,2,\ldots,n.$ We require that $p$ split completely in $K_n=\mathbb{Q}(\zeta_n)$, which is equivalent to (1), and that each factor remain prime in every extension $K_n(\sqrt[n]{a/b})/K_n$ with $a,b$ as above, which implies (2).

I am hesitant to say that it's a complete proof because my algebraic number theory is out of shape.