Residue Classes and Complete Residue Systems

We prove each part using the division algorithm, elementary properties of divisibility, and the definitions above. No part of this proof invokes any result depending on it (no circularity).

(1) Equivalence relation with exactly $n$ classes. Reflexive: $a - a = 0 = n \cdot 0$, so $n \mid (a-a)$, i.e. $a \equiv a \pmod n$. Symmetric: if $a \equiv b \pmod n$ then $n \mid (a-b)$, so $a - b = nk$ for some integer $k$; then $b - a = n(-k)$, so $n \mid (b-a)$, i.e. $b \equiv a \pmod n$. Transitive: if $a\equiv b\pmod n$ and $b \equiv c \pmod n$, write $a-b = nk$ and $b-c=nl$ for integers $k,l$. Then $a - c = (a-b)+(b-c) = n(k+l)$, so $n \mid (a-c)$, giving $a \equiv c \pmod n$. Hence $\equiv \pmod n$ is an equivalence relation, and its equivalence classes are precisely the sets $[a]_n$ defined above; they partition $\mathbb{Z}$ (standard fact about equivalence classes: any two classes are equal or disjoint, and their union is the whole set). To see there are exactly $n$ distinct classes, invoke the division algorithm: for any integer $a$ there exist unique integers $q, r$ with $a = qn + r$ and $0 \le r < n$. Then $a - r = qn$, so $n \mid (a-r)$, giving $a \equiv r \pmod n$ and hence $[a]_n = [r]_n$ with $r \in \{0,1,\dots,n-1\}$. Thus every class equals one of $[0]_n,\dots,[n-1]_n$, so there are at most $n$ classes. These $n$ classes are pairwise distinct: if $0 \le i < j \le n-1$ and $[i]_n = [j]_n$, then $i \equiv j \pmod n$, so $n \mid (j - i)$; but $0 < j - i \le n-1 < n$, so $n$ cannot divide $j-i$ (a nonzero integer of absolute value less than $n$ has no positive multiple of $n$ dividing it, since the smallest positive multiple of $n$ is $n$ itself). This contradiction shows $[i]_n \ne [j]_n$. Hence there are exactly $n$ distinct classes.

(2) Well-definedness and ring structure. Suppose $[a]_n = [a']_n$ and $[b]_n = [b']_n$, i.e. $a \equiv a' \pmod n$ and $b \equiv b' \pmod n$. Write $a' = a + kn$, $b' = b + ln$ for integers $k, l$. Then

so $[a'+b']_n = [a+b]_n$; this shows addition of classes does not depend on the representatives chosen, i.e. it is well-defined. For multiplication,

so $[a'b']_n = [ab]_n$, and multiplication is likewise well-defined. The ring axioms for $(\mathbb{Z}/n\mathbb{Z}, +, \cdot)$ now follow directly from the corresponding axioms in $\mathbb{Z}$, applied to representatives, using well-definedness to know the results do not depend on which representatives were used:

• Associativity of $+$ and $\cdot$, commutativity of $+$ and $\cdot$, and the distributive law all hold because, for representatives $a,b,c$,

and similarly for the other identities, each reducing to the corresponding true identity in $\mathbb{Z}$ inside the bracket.

• Additive identity: $[0]_n + [a]_n = [0+a]_n = [a]_n$.
• Additive inverse: $[a]_n + [-a]_n = [a + (-a)]_n = [0]_n$, so $-[a]_n := [-a]_n$.
• Multiplicative identity: $[1]_n \cdot [a]_n = [1\cdot a]_n = [a]_n$.

Hence $\mathbb{Z}/n\mathbb{Z}$ is a commutative ring with identity. By part (1) it has exactly $n$ elements, namely $[0]_n,\dots,[n-1]_n$.

(3) Characterization of complete residue systems. ($\Rightarrow$) Suppose $S = \{r_1,\dots,r_m\}$ is a CRS mod $n$, meaning every integer is congruent to exactly one $r_i$. In particular each $r_i$ is congruent to exactly one element of $S$ (namely itself), so the $r_i$ are pairwise incongruent mod $n$: if $r_i \equiv r_j \pmod n$ with $i \ne j$ then $r_i$ would be congruent to two different elements of $S$ ($r_i$ itself and $r_j$), contradicting "exactly one." Also, by part (1) every integer is congruent to exactly one of $0, 1, \dots, n-1$, hence to exactly one class among the $n$ classes; the requirement that every integer is congruent to a unique member of $S$ forces $S$ to meet every one of the $n$ classes (existence) and to contain no two elements from the same class (uniqueness, just shown). Since $S$ meets all $n$ classes and has at most one element per class, $|S| = m = n$ exactly. ($\Leftarrow$) Suppose $m = n$ and the $r_i$ are pairwise incongruent mod $n$. By part (1), each $r_i$ lies in some class $[r_i]_n$, and these $n$ classes are pairwise distinct (pairwise incongruence means precisely $[r_i]_n \ne [r_j]_n$ for $i\ne j$). Since there are exactly $n$ classes total (part 1) and we have exhibited $n$ pairwise distinct ones, $\{[r_1]_n,\dots,[r_n]_n\}$ is the full set of classes $\{[0]_n,\dots,[n-1]_n\}$. Hence every integer $x$, lying in some class, lies in exactly one $[r_i]_n$ (classes are disjoint), i.e. $x \equiv r_i \pmod n$ for exactly one $i$. This is exactly the definition of a CRS.

(4) Linear transport. Suppose $\{r_1,\dots,r_n\}$ is a CRS mod $n$ and $\gcd(a,n) = 1$. By part (3) it suffices to show the $n$ integers $ar_i + b$ are pairwise incongruent mod $n$. Suppose $ar_i + b \equiv ar_j + b \pmod n$ for some $i,j$. Subtracting $b$ from both sides (valid since congruence is preserved under adding/subtracting the same integer, an immediate consequence of the definition: if $n\mid(x-y)$ then $n \mid ((x+c)-(y+c))$), we get

Since $\gcd(a,n) = 1$, Euclid's lemma in the form "$n \mid ac$ and $\gcd(a,n)=1$ implies $n \mid c$" (a standard consequence of Bézout's identity: write $1 = ax + ny$ for integers $x,y$, then $c = acx + ncy$, and $n$ divides both terms on the right since $n \mid ac$ by hypothesis and $n \mid ncy$ trivially, so $n \mid c$) gives

Since $\{r_1,\dots,r_n\}$ is a CRS, part (3) says the $r_i$ are pairwise incongruent, forcing $i = j$. Hence $ar_1+b,\dots,ar_n+b$ are pairwise incongruent mod $n$, and there are $n$ of them, so by part (3) they form a CRS mod $n$. For the converse, suppose $\gcd(a,n) = d > 1$. Consider $r_1 = 0$ and choose (using part 3, since $\{r_i\}$ is a CRS and $n/d$ is an integer with $0 \le n/d < n$ when $d>1$... more directly) two representatives $r_i, r_j$ with $r_i - r_j = n/d$; such a pair exists among any CRS because $n/d$ is a nonzero residue mod $n$ (as $0 < n/d < n$ since $d>1$), so it equals $r_i - r_j$ for the unique $i,j$ with $r_i \equiv (r_j + n/d) \pmod n$, guaranteed to exist and be distinct by part (3) applied to the CRS $\{r_1,\ldots,r_n\}$. Then

and since $d \mid a$, $a/d$ is an integer, so $n \mid a(r_i-r_j)$, i.e. $ar_i \equiv ar_j \pmod n$, hence $ar_i + b \equiv ar_j+b \pmod n$ with $r_i \ne r_j$ so (by pairwise incongruence of the original CRS, part 3) $i \ne j$. Two of the transported values are congruent mod $n$, so by part (3) the transported set is not a CRS mod $n$ (it fails pairwise incongruence, and it still has exactly $n$ elements as a multiset but at most $n-1$ distinct residues, hence cannot cover all $n$ classes). $\blacksquare$