The only equivalence relations on $\mathbb{Z}$ that are compatible with the ring operations are congruences modulo $n$ for $n \in \mathbb{Z}$

Question

It's (probably) a fairly basic result that the only equivalence relations on $\mathbb{Z}$ that are compatible with the ring operations are congruences modulo $n$ for $n \in \mathbb{Z}$... as it's usually stated without proof in more advanced works on algebra.

(This is a "completeness result"--if you'd like to call it that--of the more elementary fact (in the opposite direction) that congruences modulo $n$ are compatible with the ring operations on $\mathbb{Z}$. The only slightly tricky part of the reverse implication is to prove it for multiplication: $a_1 - a_2 = xn$ and $b_1 - b_2 = yn$ imply that $a_1 b_1 - a_2 b_2 = a_1 (b_1 - b_2) + b_2(a_1-a_2) = (a_1 y + b_2x)n$.)

But to restate the problem at hand here, let $E$ be an equivalence relation on $\mathbb{Z}$ compatible with the ring operations, i.e E is reflexive, transitive, symmetric, and additionally that $a_1Ea_2$ and $b_1Eb_2$ imply that $(a_1+a_2)E(b_1+b_2)$ and $(a_1a_2)E(b_1b_2)$. Prove that there exist $n \in \mathbb{Z}$ such that for all integers $a,b \in \mathbb{Z}$, $aEb$ implies that $a-b = kn$ for some $k \in \mathbb{Z}$.

Answer 1

Consider the set $Z:=\{a\in \mathbb{Z}:aE0\}$. The positive integers in this set have a minimum, call it $n$. (If the only element is $0$, then $E$ is the equality relation.)

One can then prove the following statements:

1. $Z=n\mathbb{Z}$ (by using the division algorithm).
2. $aEb\iff (a-b)E(b-b)\iff (a-b)E0\iff a-b=kn$.

Answer 2

To collect here a couple of my comments that maybe someone else finds useful on this matter:

• The problem is reduced to that of determining (all the) ideals of $\mathbb{Z}$ because (as Howie phrased this):

in a ring a congruence is determined if we know the ideal which is the congruence class containing the zero.

• There can be no more ideals than there are (additive) subgroups and $n\mathbb{Z}$ are all subgroups of $\mathbb{Z}$.

• More generally, every integral & Euclidean domain is a principal ideal domain, or in Dummit and Foote's words:

The first implication of a Division Algorithm for the integral domain $R$ is that it forces every ideal of $R$ to be principal. Every ideal in a Euclidean Domain is principal. More precisely, if $I$ is any nonzero ideal in the Euclidean Domain $R$ then $I$ = ($d$), where $d$ is any nonzero element of $I$ of minimum norm.

(For $\mathbb{Z}$ the absolute of an element value gives the norm.)