Can we color Z^+ with n colors such that a, 2a, ..., na all have different colors for all a? 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 for n+1 prime, by Peter Pach Pal. 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.
Ideas. As there is a lot of discussion going on, I thought I share here my attempts as Ewan and Gowers took similar paths. First of all, if we denote the primes by $p_i$ and the largest prime not bigger than $n$ by $p_d$, then it is sufficient to color the numbers of the form $\Pi p_i^{\alpha_i}$. This is equivalent to coloring $\mathbb Z^d$ with n colors such that the translates of a special poliomino are all rainbow colored, meaning they contain all $n$ colors. This is also equivalent to tiling the space with translates of this poliomino. The easiest way to give a coloring is if we have some nice periodicity, eg. if n+1 is prime, then $\Pi p_i^{\alpha_i} \mod (n+1)$ is such, whenever we go in a direction, it corresponds to an authomorphism of $Z_{n+1}^*$. Another possibility is to give a "linear" coloring using the addition $\mod n$, for example for $n=5$, one can take $x+3y+4z \mod 5$. So far I could always find such a linear coloring but I cannot prove that it always exist, eg. we have too many constraints to use the combinatorial nullstellensatz.
 A: For n=3 I think one can argue as follows. Let's first find a colouring of N^2 with three colours such that every triangle of the form (x,y), (x+1,y), (x,y+1) gets different colours. That we can do e.g. by colouring (x,y) by x+2y mod 3. Let's call that colouring phi.
Now write any integer uniquely in the form 2^a3^bm and colour it phi(a,b). I claim that this works. Indeed, if we take this integer, twice this integer and three times this integer, then the three colours will be phi(a,b), phi(a+1,b) and phi(a,b+1).
This feels pretty similar to a special case of what Ewan was saying, but I'm not sure it's identical. And I think it may generalize quite nicely. The crucial lemma seems to be that if we define a set of points in Z^d by letting T be the intersection of Z^d with a triangle bounded by the coordinate hyperplanes and a hyperplane of the form  $a_1x_1+...+a_dx_d\leq C$, then we can colour Z^d with |T| colours in such a way that every integer translate of T gets |T| different colours. I haven't checked that statement but it feels plausible.
A: 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 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.
A:  Definition  I say that a function $f : \lbrace 1, \ldots ,n \rbrace \to \frac{\mathbb Z}
{n \mathbb Z} $ is multiplicative iff whenever $x=yz$ for $x,y,z$ in the range
of $f$, then $f(x)=f(y)+f(z)$ in $\frac{\mathbb Z}{n \mathbb Z} $. (note :this
reminds one of "Freiman homomorphisms").
Let $A_n$ denote the set of integers all of whose prime factors
are $\leq n$, and $B_n$ the set of integers all of whose prime factors
are $> n$. Any integer  can be written as a product of an element
of $A_n$ by an element of $B_n$.
Lemma 1 If $f : \lbrace 1, \ldots ,n \rbrace \to \frac{\mathbb Z}
{n \mathbb Z} $ is multiplicative,
then $f$ may be extended uniquely to a mapping $g: {\mathbb Z}^{+} \to \frac{\mathbb Z}
{n \mathbb Z} $ such that  $g$ is multiplicative on $A_n$
(i.e. $g(aa')=g(a)+g(a')$ for any $a,a' \in A_n$) and
$g(ab)=g(a)$ for any $a\in A_n,b \in B_n$.This map $g$
has the property that the image of $g(x),g(2x), \ldots ,g(nx)$
is exactly $\frac{\mathbb Z}{n \mathbb Z} $ for any $x$.
Lemma 2 Multiplicative functions 
$f : \lbrace 1, \ldots ,n \rbrace \to \frac{\mathbb Z}
{n \mathbb Z} $ do exist.
Proof of lemma 2 : first set $f(1)=0$. Now set $f(2)$ to any
nonzero value. By multiplicativity, this determines the value
of $f$ on all powers of $2$ that are $ \leq n$. Let us call $V_1$
the set of all values of $f$ obtained so far. Now set $f(3)$ to any
value . By multiplicativity, this determines the value
of $f$ on numbers $\leq n$  that are only divisible by $2$ or $3$. Let us call $V_2$
the set of all values of $f$ obtained so far, etc.
Continuing like this until all values are determined, we eventually reach
a multiplicative function.
A: This is not a solution, but ideally a clarification of the question.  The semigroup $\mathbb{Z}_+$ under addition is equivalent to the semigroup $\mathbb{Z}_{\ge 0}^\infty$ under addition.  We are interested in certain special subsets $A_n$ of the latter, which in multiplicative form correspond to $\{1,2,\ldots,n\}$.  Each $A_n$ is a certain $n$-element lower set in the natural partial ordering on $\mathbb{Z}_{\ge 0}^\infty$.  We would like to color $\mathbb{Z}_{\ge 0}^\infty$ with $n$ colors such that each translate of $A_n$ uses $n$ different colors.
By a compactness argument, we can find a sequence of translates of $\mathbb{Z}_{\ge 0}^\infty$ in $\mathbb{Z}^n$ such that the colorings converge to a coloring of all of $\mathbb{Z}^\infty$.  In other words, in multiplicative form, we could equally well have asked the question in $\mathbb{Q}_+$ as in $\mathbb{Z}_+$.
Also, I think that the subset of $\mathbb{Z}^\infty$ with color 1 is a set of vectors that yields a tiling of $\mathbb{Z}^\infty$ by translates of $-A_n$.  For instance, if two of these translates intersect at $x$, then you correspondingly $x+A_n$ contains two elements with color 1.  (Technically this only shows that it is a packing, not a tiling.  However, the cracks that are not tiled must have density 0, and you can translate them away by the same compactness argument.)  Moreover, if you have such a tiling, then you can color each element of each tile in the same way, and then for that coloring each translate $x+A_n$ has all different colors.  Again, in multiplicative form, you're tiling the positive rational numbers by arithmetic progressions $a,2a,3a,\ldots,na$.

To summarize my understanding of this problem:


*

*Every admissible coloring of $\mathbb{Z}_+$ yields a tiling of $\mathbb{Q}_+$ by subsets of the form $T_a = \{a,2a,3a,\ldots,na\}$, and vice versa.

*There is a special interest in lattice tilings, in which the set of choices of $a$ is a subgroup of $\mathbb{Q}_+$ of index $n$.  In particular, if $n+1$ or $2n+1$ is prime, then such a subgroup exists, and the quotient group is isomorphic to $\mathbb{Z}/n$.

*It is easy to make variations that do not tile $\mathbb{Q}_+$, for example multiples of $\{1,2,3,4,6,8,9\}$.  However, these variations generally span abelian groups in $\mathbb{Q}_+$ of lower rank than the span of $\{1,2,3,\ldots,n\}$.  For the stated question, the rank is $\pi(n)$, and we may as well work in the subgroup of $P_n$ of $\mathbb{Q}_+$ generated by the $\pi(n)$ primes up to $n$.


I decided to look at the problem this way:  Among all $n^{\pi(n)}$ homomorphisms from $P_n$ to $\mathbb{Z}/n$, can we heuristically estimate the number that are a bijection when restricted to $\{1,2,\ldots,n\}$?  Let's say that the restriction of such a homomorphism is not particularly more likely or less likely to be a bijection than a random function.  The latter probability is $n!/n^n$, so we can expect roughly $n!\cdot n^{\pi(n)-n}$ solutions.  We can now take a logarithm and apply Stirling's approximation and a sufficiently careful version of the prime number theorem, $\pi(n) \approx \text{Li}(n)$.  The answer is that there is plenty of entropy to have solutions; the predicted log of the number of solutions is roughly $n/(\ln n)$.  This heuristic can be checked for small $n$.  If the heuristic is reliable, then there should be solutions for all $n$.
It would be nice to have an effective construction of such a homomorphism for all $n$, but my impression is that the other answers so far don't find one.  Note the last remark in Victor's answer: "I have a truly marvelous proof of this proposition, but the margins of MO are too thin to contain it."
A: I suggested in a comment, to look for colorings that are the same for each a, except for a fixed permutation.
Suppose the colors are given by function c(x), for x ≥ 1. And a permutation function p(i,j), where i,j ∈ [1..n]. Where i is the index of the permutation, and j the index of the permutation of the color.
If n = 4 and the coloring starts with abcd, then p(1,1) = a, p(1,2) = b, p(1,3) = c, p(1,4) = d, p(2,1) = b, p(2,2) = d.
If the coloring is the same for each a, then we get the following equation:
c(an) = p(c(a),c(n))
It is more important to give a condition when the above condition is met.
Lemma 1: If p(x,y) is reflexive (p(x,y)=p(y,x)) and associative (p(x,p(y,z))=p(p(x,y),z)) and p(x,y)=p(1,xy) for xy ≤ n, then a coloring can be constructed.
Lemma 2: For each n a permutation exists such that it reflexive and associative and for p(x,y)=p(1,xy) for xy ≤ n.
To see how this works, for n = 4, we start the following permutation matrix:
abcd
bd..
c...
d...
Fill in the second row:
abcd
bdac
ca..
dc..
And complete it:
abcd
bdac
cadb
dcba
From this construct the coloring:
abcdxaxcdxxbxxxa
By each prime number a > n (the x values in the coloring), you can choose a color for c(a), but you have to continue with the permutation of that color for c(ma).
Lemma 1 is trivial to prove, because the associative and reflexive conditions makes that reaching a number by different values of a, factoring the number and re-arranging makes that it must have the same value. For the values xy ≤ n, you can't factor anymore, and the condition must just met.
I haven't proven lemma 2 fully. A permutation matrix with reflexive and associative conditions, can be constructed by starting with 1 permutation that has a single cycle. The full matrix can be constructed by applying this permutation multiple times, up to n.
It can be proven, that such matrix has the reflexive and associative condition, but not necessary the condition that p(x,y)=p(1,xy) for xy ≤ n;
The solution of François as matrix looks like this:
abcdef
bdface
cfbead
daebfc
ecafdb
fedcba
The permutation from first row to second row is not a permutation with a single cycle. It brings you from row 1, to row 2 to row 4, back to row 1. However, this can still be categorized as 1 cycle permutation, because the permutation from first row to third row, is a permutation with a single cycle.
Instead of looking at the permutation per color, it is better to look which colors are passed, when the permutation is applied multiple times. In above example the cycle is (first row to third row) a->c->b->f->d->e->a. 
If we just make the second row a permutation with one cycle, then the cycle starts with:
1->2->4->8->16->32->64 etc. Then we can add 3 and the other primes.
For n = 27 we can get:
1->2->4->8->16->3->6->12->24->x->9->18->5->10->20->27->x->15->7->14->11->22->x->21->25->13->26->1
In above sequence, multiplications with 2, have 1 step, multiplication with 3, 5 steps, multiplications with 5 have 12 steps. The remaining primes 17, 19, 23 can be placed on any of the x values. The short parts 11->22 and 13->26 can easily be exchanged. From this cycle, you can make a permutation and permutation matrix that has the condition that p(x,y) = p(1,xy) for xy ≤ n. From that permutation the coloring can be constructed.
As you can see, it is not very difficult to construct a coloring this way. But, the sequence is also rather crowded. It is not a prove yet that it is always possible.
