Every equivalence relation on $\mathbb{Z}$ that is compatible with the addition structure is either the identity or the relation $\equiv \pmod{n}$

Question

Let $R$ be an equivalence relation on $\mathbb{Z}$ such that the operation on the quotient set $\mathbb{Z}/R$ given by the rule $[x]_R + [y]_R = [x+y]_R$ is well-defined. Show that $R$ must either be the identity relation ($x R\, y \iff x = y$) or the relation "mod $n$" for some $n$.

It's easy to show that the two relations satisfy the operations on the quotient set $\mathbb{Z}/R$. I'm having trouble proving there does not exist another relation such that it satisfies operations on the quotient set.

Answer 1

Hint: Given a relation $R$, Show that the elements related to $0$ is a subgroup of $\mathbb{Z}$.

Answer 2

Note that $\mathbb{Z}/R$ is a group because $[0]_R+[g]_R=[0+g]_R=[g]_R$ so $[0]_R$ is the identity, and associativity can be proved similarly.

If $R$ is not the identity relation, then $\exists n,n'\in\mathbb{Z}$ such that $nR\,n'$ and $n\neq n'$. It follows that $[n-n']_R=[n]_R-[n']_R=[0]_R$ and so $(n-n')R\,0$. As the set of positive elements related to $0$ is non-empty (if $n-n'$ is negative then $n'-n$ is positive and $(n'-n)R\,0$ still), we can choose the least positive $m$ satisfying $mR\,0$.

Now, for all $k\in\mathbb{Z}$, $k=pm+q$ for some $p\in\mathbb{Z}$ and $q\in\{0,1,\ldots m-1\}$. Hence $$[k]_R=[pm+q]_R=[pm]_R+[q]_R=[m]_R+\cdots +[m]_R+[q]_R=[q]_R$$ which means that $kR\, q$ and so $R$ relates all integers with the same remainder mod $m$. In particular, $\mathbb{Z}/R$ is at least a subgroup of $\mathbb{Z}/m\mathbb{Z}$ and so is cyclic, hence $R$ is a modulo relation. We can actually show that $R$ can not be 'larger' than this relation, as we get this automatically by the fact that $m$ was chosen to be minimal, and if there were any other relations except modulo $m$, then we could have chosen an $m'$ smaller than $m$ which is a contradiction.