We will start from some element $a$ and show that we can equate it with any other element of $M$. First, we note that if $a \equiv b \mod{k}$, $a$ and $b$ have the same color, so it is only necessary to show that all residues modulo $k$ are the same color. Also, $a \mod{k}$ and $n-a \mod{k}$ have the same color, as given. (1) By the second condition, we can also infer that $a \mod{k}$ and $-a \mod{k}$ (2) are the same color because we just take an element $x \equiv a \mod{k}$ such that $x < k$ and we have $x \equiv a \mod{k}$ and $|x-k| = k-x \equiv -x \equiv -a \mod{k}$ the same color. So we generate residues (all $\mod{k}$) as follows. If $mn+a$ is blue for some integer $m$, we have $-mn-a$ is blue by (2) and $n-(-mn-a) = (m+1)n+a$ is blue by (1). Hence by induction all $mn+a$ are blue. But noting that $(n,k) = 1$, $mn+a$ clearly takes on all residues modulo $k$ and the proof is complete.

If $a$ is blue and $a>k$ then we see that $a-k$ is also blue. If $a<k$ then $a$ $k-a$ and $n+a-k$ have this same color. We can write that for all $a \not = k$ $a$ and $a-k$ (mod n) have that same color. All the numbers we will consider $(mod n)$. Let's assume that $-k (mod n)$ is blue. By induction we have that $-lk (mod n)$ is also blue for $l=1...,n-1$. If $-l_{1}k \equiv-l_{2}k (mod n)$ we have that $l_{1}=l_{2}$ and for only l=n-1 $-lk=k (mod n)$. So all the numbers $-lk (mod n)$ are diffrent and there are n-1 of them.

We know that $ ka\bmod n$, $ k$ and $ n$ relatively prime and $ a$ ranging from $ 0$ to $ n - 1$ constitutes a complete residue system mod $ n$. Let $ k(n - 1) \equiv q \bmod n$, $ 1 \leq q \leq n - 1$ (since q is nonzero). Let $ q$ be blue. Consider $ q - ka \bmod n$. For different $ a$, we have different residues $ \mod n$. Also, by the definition of $ q$, $ q - ka$ is nonzero $ \mod n$ for $ 0 \leq a \leq n - 2$. Therefore we may produce $ n - 1$ distinct, nonzero residues $ \mod n$, all the same color, completing the proof.

I think I am missing something as this seems too easy. Suppose that 1 is Blue. Then note that for all $k \in \{ 3,\dots,n-1 \},\text{gcd}(1,k) = 1.$ So, $1$ and $|1-3| = 2$ have same color. In this way we find that all the numbers upto n-2 have the same color as 1. Then by the first condition, 1 and n-1 have the same color, and hence all the elements have the same color.

limac wrote: I think I am missing something as this seems too easy. Suppose that 1 is Blue. Then note that for all $k \in \{ 3,\dots,n-1 \},\text{gcd}(1,k) = 1.$ So, $1$ and $|1-3| = 2$ have same color. In this way we find that all the numbers upto n-2 have the same color as 1. Then by the first condition, 1 and n-1 have the same color, and hence all the elements have the same color. $k$ was one fixed number.

Two words: careful Bezout Because of the second rule, if $a \equiv b$ (mod $k$) and both are in $M$, then they have the same color ($ b > a \Rightarrow b > k$). Using this then with $a < k$ we see that if $a \equiv -b$ (mod $k$) and both are in $M$, then they have the same color (since $k<n$). Also, since $i$ and $n-i$ have the same color, we see that if $a+b \equiv n$ (mod $k$), and both are in $M$, then they have the same color. Since $k<n$, all congruences modulo $k$ occur in $M$. The congruence of $i$ will have the same color as that of $-i$ which will have the same color as $n+i$. Because $(n,k)=1$ we see that the congruence of $b=a+nk$ (where $b$ is anyone) will have the same color as the congruence of $a$. So $a$ and $b$ will always have the same color if both are in $M$. Done.

Extend the coloring to all integers in a way such that 0 is colored the same way as $k$, and otherwise the coloring of $i+n$ is identical to the coloring of $i$. The rest of the proof is a careful argument that the coloring has period $k$; let the set of all numbers $i$ such that $i$ and $i-k$ have the same coloring be $S$. Obviously by the given condition, any numbers congruent to $k, k+1, k+2, \cdots, n-1$ mod $n$ are in $S$. Now, suppose $i$ is congruent to 0 through $k-1$ modulo $n$. Define $a \sim b$ between two positive integers $a, b$ to show that $a, b$ have the same coloring. Then, $$i-k \sim n+i-k = n-(k-i)\sim k-i \sim i$$by the second condition, so these numbers are in $S$ as well. This means that the coloring is periodic with periods $n$ and $k$. But $\gcd(n, k) = 1$, so this implies all numbers have the same color, as desired.

To remove the absolute value, extend the coloring by adjoing ad infinitum the block in brace to the left $$ \cdots [\bullet, n-1, n-2, \dots, 1, \bullet, 1, \dots, 1, \dots, n-1][\bullet, n-1, n-2, \dots, 1, \bullet, 1, \dots, 1, \dots, n-1]\cdots $$Then, it is given that the elements in positions $i-k$ and $i-n$ are painted the same color as the element in position $i$, as long as none of these is in a position with a $\bullet$. Since $(n, k)=1$, it is now clear that starting from 1, we may reach every other residue $\pmod n$ by subtracting $k$ and $n$: we just need to be careful and subtract $n$ whenever subtracting $k$ would land us on a $\bullet$.

Add zero to $M$ with the same color as $k$. So the condition where $i \ne k$ in $M$ satisfy $i$ and $|i - k|$ having the same color still holds. Notice that for $i \ge k$, we have that $i$ is the same color as $i - k$. Thus, all numbers of the same residue modulo $k$ are of the same color. Now for any integer $x$, let the color of $x$ be the color of the remainder when $x$ is divided by $k$. Let $a \iff b$ mean that $a$ and $b$ have the same color. Note that $a \iff b$ if and only if $a + k \iff b + k$. Therefore, $i \iff n - i$ for each $i$ (this is true for $i = 1, 2,\ldots, k$ and then we can shift $i$ by any multiple of $k$). Also for any $i \in \{0,1,\ldots, k - 1\}$, we have $i \iff |i - k| = k - i$, so $i \iff -i$. This means that $i \iff -i \iff n - (-i) = n + i$, so $i \iff i + N n$ for any positive integer $N$. This can take any residue modulo $k$, so we are done.