First of all, congratulations to [Dömötör][1]! This question is related to an interesting [problem][2] he asked a while ago. (And it is an attempt to have people take a new look at that problem.)

Let me recall the setting of domotorp's question. Here I am only looking at colorings of ${\mathbb Z}^+$ using 6 colors. We require that, for any positive $a$, the numbers $a,2a,\dots,6a$ all receive different colors.

Trying to build such a coloring, it is easy to see that we only need to worry about coloring the set of positive integers of the form $2^a3^b5^c$ (that I call $K$, for `core').

There is a natural approach, suggested by Ewan Delanoy. Let's say that the coloring $c$ is multiplicative if it is induced by a `partial homomorphism' from {$1,\dots,6$\} to ${\mathbb Z}/6{\mathbb Z}$. This means that $$c(2^a3^b5^d)=ac(2)+bc(3)+dc(5)\mod6.$$

Multiplicative colorings can be represented in nice ways, see for example the suggestion by Victor Protsak. 

Not all 6-colorings are multiplicative, though. ($n=6$ is the least number of colors for which this happens.) 

For example, there is a coloring with $c(1)=c(12)=c(25)=c(40)=c(45)=c(96)=c(108)=\dots$; $c(2)=c(9)=c(16)=c(30)=c(72)=c(100)=\dots$; $c(3)=c(10)=c(24)=c(27)=c(80)=c(90)=\dots$; $c(4)=c(15)=c(32)=c(36)=c(50)=c(120)=\dots$; $c(5)=c(8)=c(18)=c(60)=c(64)=\dots$; and $c(6)=c(20)=c(48)=c(54)=c(75)=\dots$

This is not multiplicative. The only multiplicative $c$ with $c(8)=c(5)$ must have $c(9)=c(4)$.

> My question is whether there is a
> reasonable algebraic characterization
> of non-multiplicative colorings, or at
> least of some interesting subfamily of
> these. (And if the answer is yes, I
> wouldn't object to seeing something
> about general $n$.)

The examples I have, all come equipped with some obvious structure, and what I would like is to understand what  is really going on. What I would hope for is something akin to the notion of `partial homomorphism', but at the moment I really don't know what to expect.

  [1]: http://arxiv.org/abs/1009.4641
  [2]: http://mathoverflow.net/questions/26358/can-we-color-z-with-n-colors-such-that-a-2a-na-all-have-different-colors