first, we can easily prove that if $j| a-b$ then $a$ and $b$ receive the same color. let $1 \le c<j$ be chosen arbitrarily. then $c$ , $j-c$ and $n-c$ receive the same color. putting $c:=j-c$ we obtain that $c+(n-j)$ receive this color too. now the problem becomes trivial since $(n-j,j)=1$

Dumel wrote: first, we can easily prove that if $j| a-b$ then $a$ and $b$ receive the same color. Could you explain why?

Indeed, the proof is slightly criptic. Let's make it more palatable. Before anything else, augment $N$ with elements $0$ and $n$, to which we will assign the color of $j$, so now (ii) also works for $i=j$ (this will serve later, when we work modulo $j$). We will denote by $a \sim b$ the fact that $a$ and $b$ bear the same color, blatantly an equivalence relation. If $a < b$, $j \mid b - a$, it means $b=a+kj$, for some positive integer $k$. Then, by dint of (ii), we have $b = a+kj \sim a+(k-1)j \sim \cdots \sim a + j \sim a$, and so $a\equiv b \pmod{j}$ implies $a \sim b$. For any $0\leq c < j$ we are told that $c \sim j-c$ and $j-c \sim n - (j-c) = (c+n) - j$. But $(c+n)-j \equiv c+n \pmod{j}$, therefore $c \sim j-c \sim (c+n) - j \sim c+n$. It follows that modulo $j$ we have $c\sim c+n \sim c + 2n \sim \cdots \sim c+(j-1)n$. But since $\gcd(n,j) = 1$, it follows that modulo $j$ the elements $c,c+n,c+2n,\ldots,c+(j-1)n$ are a complete system of residues, therefore they are some permutation of $0,1,2,\ldots,j-1$, and so $0\sim 1 \sim 2 \sim \cdots \sim j-1$, and we are done. Addendum. There is a slight connection with similar problems, where the Wilf-Fine theorem proves to be instrumental.

amparvardi wrote: Each of the numbers in the set $N = \{1, 2, 3, \cdots, n - 1\}$, where $n \geq 3$, is colored with one of two colors, say red or black, so that: (i) $i$ and $n - i$ always receive the same color, and (ii) for some $j \in N$, relatively prime to $n$, $i$ and $|j - i|$ receive the same color for all $i \in N, i \neq j.$ Prove that all numbers in $N$ must receive the same color. WLOG that $1$ is red. Now, $j-1$ and $n-1$ are also both red. In addition, $n-j+1$ is red. So is $j-1$, as $(n-j+1)+(j-1)=n$. Okay, so in general if $k<j$ is red, so are $j-k$ and $n-k$. This means that then $n-j+k$ is red. Then we can see that adding $n-j$ to the element number does not change the color (j-1,n-1),...(1,n-j+1) are all same color pairs. In fact, this thing is periodic with period $n-j$ (the case $j=n-1$ is quite trivial though, so otherwise this has greater periodicity). Okay, so then if $k$ is some color, so are $n-k$ and $n-j+k$, as well as $j+k$. Then, we see that this is periodic with period $j$ as well. This is periodic with period $j$, periodic with period $n-j$, and is the same reversed. let $j=m$, $n-j=p$. Note this implies that the color on $1$ is then the color on $p+1$ and on $m+1$. I claim it is always the color on $am+bp+1$ as well where $a$ and $b$ are integers (can be negative), as long as that value is within the range $1$ to $n-1$. This is not too hard to see. That is, we assume that some values less than $m$ and $p$ work, then use strong induction. Note one of $a(m+1)+bp$ and $am+b(p+1)$ lies in this range desired, as does one of $a(m+1)+bp$ and $am+b(p-1)$. We can just then induct on $a-b$ and use our construction, adding or subtracting 1 from $a-b$ or adding $1$ to it to get that everything $am+bp+1$ works. As $a$ and $b$ are relatively prime, by Chicken Mc Nugget anything at most $ab-a-b-1+1$ (with the +1 coming from the +1 in $am+bp$ PLUS ONE) that is a positive integer bigger than $1$ can be written like this and thus such positive integers in the range have the same color as $1$. Note that this is $(a-1)(b-1)+1=(n-j-1)(j-1)+1$. When $2<=j<=n-2$ this is at least $n-2$ but then $n-1$ is the same color as $1$ anyway, so we are done then as every integer can be written like this and colored the same color as $1$. Note the more $j$ deviates from $n/2$, the further apart $n-j-1$ and $j-1$, who have constant sum are, and the bigger this value will be. Then $j=1$ gives that $n$ and $n+1$ are the same value anyway, trivializing the problem. Also $j=n-1$ gives that $n-k$ and $n-k-1$ are the same value for all $k$ between $1$ and $n-1$ inclusive, so this works as well. These last two cases are quite trivial. We are done. Sorry if this was hard to understand. I will try to clarify some parts later.