Unit 3: Theory of Congruences & The Chinese Remainder Theorem

1. The Congruence Relation

The concept of congruence, introduced by Carl Friedrich Gauss in his masterpiece Disquisitiones Arithmeticae (1801), revolutionized number theory by framing divisibility in algebraic terms.

Definition 3.1 (Congruence Modulo $m$): Let $m \in \mathbb{N}$ be a positive integer (called the modulus). Two integers $a, b \in \mathbb{Z}$ are said to be congruent modulo $m$, written:

if $m$ divides their difference: $m \mid (a - b)$. If $m \nmid (a - b)$, they are incongruent, written $a \not\equiv b \pmod m$.

Theorem 3.1 (Equivalence Relation): Congruence modulo $m$ is an equivalence relation on the set of integers $\mathbb{Z}$:

1. Reflexivity: $a \equiv a \pmod m$ for all $a \in \mathbb{Z}$.
2. Symmetry: If $a \equiv b \pmod m$, then $b \equiv a \pmod m$.
3. Transitivity: If $a \equiv b \pmod m$ and $b \equiv c \pmod m$, then $a \equiv c \pmod m$.

2. Arithmetic of Congruences

Theorem 3.2 (Compatibility with Arithmetic Operations): If $a \equiv b \pmod m$ and $c \equiv d \pmod m$, then:

1. Addition: $a + c \equiv b + d \pmod m$.
2. Subtraction: $a - c \equiv b - d \pmod m$.
3. Multiplication: $a c \equiv b d \pmod m$.
4. Exponentiation: $a^k \equiv b^k \pmod m$ for every positive integer $k \ge 1$.
5. Polynomial evaluation: If $P(x) \in \mathbb{Z}[x]$ is a polynomial with integer coefficients, then $P(a) \equiv P(b) \pmod m$.

Theorem 3.3 (Cancellation Law for Congruences): If $a c \equiv b c \pmod m$, then:

In particular, if $\gcd(c, m) = 1$, we can cancel $c$ directly: $a \equiv b \pmod m$.

3. Residue Classes and the Ring $\mathbb{Z}/m\mathbb{Z}$

The equivalence classes of $\mathbb{Z}$ modulo $m$ are called residue classes (or congruence classes):

There are exactly $m$ pairwise disjoint residue classes:

Endowed with class addition $[a] + [b] = [a + b]$ and multiplication $[a][b] = [ab]$, $\mathbb{Z}/m\mathbb{Z}$ forms a commutative ring with identity $[1]$.

1. Complete Residue Systems

Definition 3.2 (Complete Residue System): A set of $m$ integers $\{r_1, r_2, \dots, r_m\}$ is called a complete residue system modulo $m$ (CRS) if every integer $x \in \mathbb{Z}$ is congruent to exactly one element of the set modulo $m$. The standard CRS is $\{0, 1, 2, \dots, m - 1\}$ (least non-negative residues).

Theorem 3.4 (Linear Transformation of a CRS): If $\{r_1, r_2, \dots, r_m\}$ is a CRS modulo $m$ and $\gcd(a, m) = 1$, then for any integer $b \in \mathbb{Z}$, the set:

is also a complete residue system modulo $m$.

2. Reduced Residue Systems and Euler's Totient $\phi(m)$

Definition 3.3 (Reduced Residue System): A set of integers $\{r_1, r_2, \dots, r_k\}$ is called a reduced residue system modulo $m$ (RRS) if:

1. $\gcd(r_i, m) = 1$ for all $1 \le i \le k$.
2. $r_i \not\equiv r_j \pmod m$ for all $i \ne j$.
3. Every integer $x$ with $\gcd(x, m) = 1$ is congruent to some $r_i$ modulo $m$.

The number of elements in any RRS modulo $m$ is denoted by $\phi(m)$ (Euler's totient function):

3. The Multiplicative Unit Group $(\mathbb{Z}/m\mathbb{Z})^\times$

Theorem 3.5 (Invertible Elements Modulo $m$): A residue class $[a] \in \mathbb{Z}/m\mathbb{Z}$ has a multiplicative inverse $[x]$ (meaning $[a][x] = [1] \iff ax \equiv 1 \pmod m$) if and only if:

The set of all invertible residue classes forms an abelian group of order $\phi(m)$ under modular multiplication, denoted $(\mathbb{Z}/m\mathbb{Z})^\times$ or $U(m)$.

1. The General Linear Congruence

Definition 3.4 (Linear Congruence): A linear congruence in one unknown $x$ is an equation of the form:

where $a, b \in \mathbb{Z}$ and $m \in \mathbb{N}$. A solution is an integer $x_0$ such that $a x_0 \equiv b \pmod m$. Two solutions $x_1, x_2$ are regarded as identical if $x_1 \equiv x_2 \pmod m$.

2. Solvability and Number of Solutions

Theorem 3.6 (Complete Solution of $a x \equiv b \pmod m$): Let $d = \gcd(a, m)$.

1. If $d \nmid b$, the congruence $a x \equiv b \pmod m$ has no solutions.
2. If $d \mid b$, the congruence has exactly $d$ mutually incongruent solutions modulo $m$.
3. If $x_0$ is any particular solution, the complete set of $d$ incongruent solutions modulo $m$ is:

Proof: The congruence $a x \equiv b \pmod m$ is equivalent to the statement:

for some integer $y \in \mathbb{Z}$. This is precisely the linear Diophantine equation in two variables studied in Unit 1 (Theorem 1.4). By Theorem 1.4, an integer solution exists if and only if $d = \gcd(a, m) \mid b$. When $d \mid b$, let $(x_0, y_0)$ be a particular solution. By Theorem 1.5, all integer solutions for $x$ are given by:

Now we determine how many of these solutions are distinct modulo $m$. Two solutions $x(t_1)$ and $x(t_2)$ are congruent modulo $m$ if and only if:

Dividing through by $\frac{m}{d}$:

Therefore, the values $t = 0, 1, 2, \dots, d - 1$ yield mutually incongruent solutions modulo $m$, and any other integer $t$ produces a solution congruent to one of these $d$ values! $\blacksquare$

Corollary 3.1 (Unique Modular Inverse): If $\gcd(a, m) = 1$, the congruence $a x \equiv 1 \pmod m$ has a unique solution modulo $m$, called the modular inverse of $a$, denoted $a^{-1}$ or $\bar{a}$. The solution to $a x \equiv b \pmod m$ is then simply $x \equiv a^{-1} b \pmod m$.

1. Statement of the Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) originated in the 3rd-century work Sunzi Suanjing (Master Sun's Mathematical Manual).

Theorem 3.7 (The Chinese Remainder Theorem): Let $m_1, m_2, \dots, m_k \in \mathbb{N}$ be pairwise relatively prime positive integers:

Let $a_1, a_2, \dots, a_k \in \mathbb{Z}$ be arbitrary integers. Then the system of simultaneous congruences:

has a unique solution modulo the total product $M = m_1 m_2 \cdots m_k = \prod_{i=1}^k m_i$.

2. Constructive Proof and Algorithm

Proof (Existence): Let $M = m_1 m_2 \cdots m_k$. For each $i \in \{1, 2, \dots, k\}$, define the partial product:

Note that $M_i$ is the product of all moduli except $m_i$. Since the moduli are pairwise coprime, $\gcd(M_i, m_i) = 1$. By Corollary 3.1, $M_i$ has a unique modular multiplicative inverse modulo $m_i$:

Now construct the integer:

We check this candidate against each congruence $j \in \{1, \dots, k\}$: For any $i \ne j$, $m_j$ divides $M_i$, so $a_i M_i y_i \equiv 0 \pmod{m_j}$. For $i = j$, $M_j y_j \equiv 1 \pmod{m_j}$, so $a_j M_j y_j \equiv a_j (1) \equiv a_j \pmod{m_j}$. Thus:

This holds for all $j \in \{1, \dots, k\}$, proving existence.

Proof (Uniqueness): Suppose $x_1$ and $x_2$ are two solutions to the system. Then $x_1 \equiv a_i \pmod{m_i}$ and $x_2 \equiv a_i \pmod{m_i}$ for all $i$. Thus $x_1 - x_2 \equiv 0 \pmod{m_i} \implies m_i \mid (x_1 - x_2)$ for all $i$. Since $m_1, \dots, m_k$ are pairwise coprime:

Therefore, $M \mid (x_1 - x_2) \implies x_1 \equiv x_2 \pmod M$. $\blacksquare$

1. Lagrange's Theorem on Polynomial Roots Modulo a Prime

Theorem 3.8 (Lagrange's Theorem on Polynomial Congruences, 1768): Let $p$ be a prime number and let:

be a polynomial of degree $n \ge 1$ with integer coefficients, such that $c_n \not\equiv 0 \pmod p$. Then the congruence:

has at most $n$ incongruent solutions modulo $p$.

Proof (by Mathematical Induction on $n$): Base case ($n = 1$): $f(x) = c_1 x + c_0 \equiv 0 \pmod p \iff c_1 x \equiv -c_0 \pmod p$. Since $c_1 \not\equiv 0 \pmod p$, $\gcd(c_1, p) = 1$. By Theorem 3.6, there is exactly $1$ solution modulo $p$.

Inductive Step: Assume the theorem holds for all polynomials of degree $k < n$. Consider a polynomial $f(x)$ of degree $n$. If $f(x) \equiv 0 \pmod p$ has no solutions, the theorem holds vacuously ($0 \le n$). Suppose it has at least one root $x_0$, so $f(x_0) \equiv 0 \pmod p$. By the polynomial division algorithm:

where $q(x)$ has degree $n - 1$ with leading coefficient $c_n$, and $R$ is a constant. Setting $x = x_0$: $f(x_0) = 0 + R \implies R = f(x_0) \equiv 0 \pmod p$. Thus:

Let $x_1$ be any other root of $f(x) \equiv 0 \pmod p$ with $x_1 \not\equiv x_0 \pmod p$. Then:

By Euclid's Lemma (Theorem 1.6), since $p \nmid (x_1 - x_0)$, we must have:

Thus, every root of $f(x)$ distinct from $x_0$ must be a root of $q(x) \equiv 0 \pmod p$. Since $q(x)$ has degree $n - 1$, by the induction hypothesis it has at most $n - 1$ roots modulo $p$. Together with $x_0$, $f(x)$ has at most $1 + (n - 1) = n$ roots modulo $p$. $\blacksquare$

2. Hensel's Lemma ($p$-Adic Root Lifting)

Hensel's Lemma is the number-theoretic analogue of Newton's method for finding roots of functions.

Theorem 3.9 (Hensel's Lemma): Let $f(x) \in \mathbb{Z}[x]$ and let $r$ be a solution to $f(x) \equiv 0 \pmod{p^k}$ for $k \ge 1$. Let $f'(x)$ denote the formal derivative of $f(x)$. If $f'(r) \not\equiv 0 \pmod p$, then $r$ lifts uniquely to a solution $s$ modulo $p^{k+1}$: