Q:

Colors on sets $S=\{1,2 \cdots ,1000\}$.

To each element of  sets $S=\{1,2 \cdots ,1000\}$ a color is assigned. Suppose that for any two elements $a$ and $b$, of $S$,if $15$ divides $a+b$, then they both are assigned with same color. What is the maximum possible number of distinct colors used?
Please provide some hints.

A:

One hint: If $a\equiv b\pmod{15}$, then choose some $c\equiv -a\pmod{15}$ -- this can easily be done with $c\in S$. Then $a$ and $c$ must have the same color, and $c$ and $b$ must also have the same color. Thus within each residue class only one color can be used -- and sometimes different residue classes also need to share one color.

