5.2 Divisibility, Congruences and the Chinese Remainder Theorem
The arithmetic of $\mathbb{Z}$ from the ground up: the division algorithm, Bézout's identity and Euclid's algorithm, unique factorisation, linear Diophantine equations, congruences, the Chinese Remainder Theorem, and the theorems of Fermat and Wilson.
Number theory is the oldest branch of algebra and still one of the most useful. Every statement in this section is about the familiar integers, yet the ideas — dividing with remainder, the greatest common divisor as the smallest positive combination $ax+by$, computing "modulo $n$" — are exactly the ideas that later become Euclidean domains, principal ideals, quotient rings $\mathbb{Z}/n\mathbb{Z}$ and the decomposition of finite abelian groups (Chapters 6–8). When you meet "$\mathbb{Z}$ is a PID" in §7.2 or "$\mathbb{Z}_{mn}\cong\mathbb{Z}_m\times\mathbb{Z}_n$ when $\gcd(m,n)=1$" in §6.2, you will be meeting the theorems of this section in new clothes.
The same ideas run modern life. Every secure web connection uses modular exponentiation and the Euclidean algorithm (RSA and elliptic-curve cryptography), ISBN and bank-card check digits are congruences, and computer hardware speeds up big-number arithmetic by splitting it with the Chinese Remainder Theorem. In CSIR NET the topic appears in almost every paper: remainders of huge powers, the number of solutions of a congruence, systems of congruences, the last digits of $a^k$, and "which of the following is always divisible by…" questions. All of them reduce to a handful of theorems that we now prove carefully.
Divisibility, the Division Algorithm and the gcd
We work in $\mathbb{Z}$ and use one property of $\mathbb{N}=\{1,2,3,\dots\}$ constantly: the well-ordering principle — every nonempty set of non-negative integers has a least element. It is equivalent to mathematical induction.
For integers $a,b$ we say $a$ divides $b$, written $a\mid b$, if $b=ac$ for some $c\in\mathbb{Z}$; then $a$ is a divisor (factor) of $b$ and $b$ a multiple of $a$. We write $a\nmid b$ otherwise. Every $a$ divides $0$; $0$ divides only $0$.
An integer $p\gt1$ is prime if its only positive divisors are $1$ and $p$; an integer $n\gt1$ that is not prime is composite, i.e. $n=ab$ with $1\lt a,b\lt n$. The number $1$ is neither prime nor composite.
- $a\mid b$ and $b\mid c$ $\Rightarrow$ $a\mid c$ (transitivity);
- $a\mid b$ and $a\mid c$ $\Rightarrow$ $a\mid bx+cy$ (divisors of two numbers divide every integer combination);
- $a\mid b$ and $b\ne0$ $\Rightarrow$ $|a|\le|b|$;
- $a\mid b$ and $b\mid a$ $\Rightarrow$ $a=\pm b$.
Proof. (1) $b=ak$, $c=bl$ give $c=a(kl)$. (2) $b=ak$, $c=al$ give $bx+cy=a(kx+ly)$. (3) If $b=ac$ with $b\ne0$, then $c\ne0$, so $|c|\ge1$ and $|b|=|a||c|\ge|a|$. (4) If $a=0$ then $b=0$ (as $a\mid b$). Otherwise $b\ne0$ too and (3) gives $|a|\le|b|\le|a|$. ∎
Proof. Existence. Let $S=\{a-bk:\ k\in\mathbb{Z},\ a-bk\ge0\}$. It is nonempty: $k=-|a|$ gives $a+b|a|\ge a+|a|$, and $a+|a|\ge0$. By well-ordering $S$ has a least element $r=a-bq\ge0$. If $r\ge b$, then $r-b=a-b(q+1)$ would be a smaller element of $S$; hence $0\le r\lt b$.
Uniqueness. If $a=bq+r=bq'+r'$ with $0\le r,r'\lt b$, then $b(q-q')=r'-r$, so $b\mid r'-r$ while $|r'-r|\lt b$. By Theorem 5.16(3) this forces $r'-r=0$, and then $q=q'$ because $b\ne0$. ∎
Be careful with negative $a$: the remainder is always non-negative, so $-17=5\cdot(-4)+3$ and $(-17)\bmod5=3$, not $-2$.
Let $a,b$ be integers, not both $0$. The greatest common divisor $\gcd(a,b)$ is the largest integer dividing both $a$ and $b$ (it exists: the common divisors are bounded by $\max(|a|,|b|)$ and include $1$). We set $\gcd(0,0)=0$. Integers with $\gcd(a,b)=1$ are coprime (relatively prime). Integers $a_1,\dots,a_k$ are pairwise coprime if $\gcd(a_i,a_j)=1$ for all $i\ne j$.
For nonzero $a,b$ the least common multiple $\operatorname{lcm}(a,b)$ is the smallest positive integer divisible by both.
- $d=\gcd(a,b)$; in particular there are integers $x,y$ with $ax+by=\gcd(a,b)$;
- every common divisor of $a$ and $b$ divides $\gcd(a,b)$;
- $L=d\mathbb{Z}$: the integers of the form $ax+by$ are exactly the multiples of $\gcd(a,b)$.
Proof. $L$ contains $a\cdot a+b\cdot b=a^2+b^2\gt0$, so it has positive elements and, by well-ordering, a least one, $d=ax_0+by_0$.
$d$ divides $a$. Divide: $a=dq+r$ with $0\le r\lt d$. Then $r=a-dq=a(1-qx_0)+b(-qy_0)\in L$. Since $r\lt d$ and $d$ is the least positive element of $L$, $r$ is not positive: $r=0$. So $d\mid a$, and likewise $d\mid b$.
$d$ is the greatest common divisor, and (2). If $c\mid a$ and $c\mid b$, then $c\mid ax_0+by_0=d$ by Theorem 5.16(2), so $|c|\le d$. Thus $d$ is a common divisor that every common divisor divides; in particular it is the largest one.
(3). Every multiple $kd=a(kx_0)+b(ky_0)$ lies in $L$, and every element $ax+by$ of $L$ is divisible by $d$ (as $d\mid a$, $d\mid b$). ∎
In the language of Chapter 7: the ideal $a\mathbb{Z}+b\mathbb{Z}$ generated by $a$ and $b$ is principal, generated by $\gcd(a,b)$. The proof above — "take the least positive element, divide by it, the remainder must vanish" — is exactly the proof that every Euclidean domain is a principal ideal domain (§7.2).
- Coprimality criterion. $\gcd(a,b)=1$ if and only if $ax+by=1$ for some integers $x,y$.
- Euclid's lemma. If $a\mid bc$ and $\gcd(a,b)=1$, then $a\mid c$.
- If $a\mid c$, $b\mid c$ and $\gcd(a,b)=1$, then $ab\mid c$. More generally, if $m_1,\dots,m_k$ are pairwise coprime and each divides $c$, then $m_1m_2\cdots m_k\mid c$.
- If $\gcd(a,b)=1$ and $\gcd(a,c)=1$, then $\gcd(a,bc)=1$.
- If $d=\gcd(a,b)\ne0$ then $\gcd(a/d,\,b/d)=1$; and $\gcd(ma,mb)=|m|\gcd(a,b)$.
- For nonzero $a,b$: $\gcd(a,b)\cdot\operatorname{lcm}(a,b)=|ab|$, and every common multiple of $a,b$ is a multiple of $\operatorname{lcm}(a,b)$.
Proof. (1) "Only if" is Bézout. Conversely, if $ax+by=1$, every common divisor of $a,b$ divides $1$.
(2) Write $ax+by=1$ and multiply by $c$: $c=acx+bcy$. Now $a\mid acx$ and $a\mid bc$, so $a\mid c$.
(3) Write $c=ak$. Then $b\mid ak$ with $\gcd(b,a)=1$, so $b\mid k$ by (2), say $k=bl$, and $c=abl$. For $k$ moduli use induction: $m_1\cdots m_{k-1}\mid c$ by hypothesis, and $\gcd(m_1\cdots m_{k-1},m_k)=1$ by (4).
(4) From $ax+by=1$ and $au+cv=1$, multiplying: $a(\ldots)+bc\,(yv)=1$, where $(\ldots)=xau+xcv+byu$. Apply (1).
(5) Dividing $ax+by=d$ by $d$ gives $(a/d)x+(b/d)y=1$; apply (1). For the second claim, the least positive value of $max+mby$ is $|m|$ times the least positive value of $ax+by$.
(6) Let $d=\gcd(a,b)$, $a=da'$, $b=db'$ with $\gcd(a',b')=1$, and assume $a,b\gt0$. Then $\ell=da'b'$ is a common multiple. If $c$ is any common multiple, $c=ak=da'k$ and $db'\mid da'k$, so $b'\mid a'k$, hence $b'\mid k$ by (2): $c$ is a multiple of $da'b'$. So $\ell=\operatorname{lcm}(a,b)$, and $d\ell=d^2a'b'=ab$. ∎
Euclid's algorithm
Bézout's theorem proves that $x,y$ exist; Euclid's algorithm (c. 300 BCE) finds them, and finds the gcd without factorising — which matters, because factorising large numbers is believed to be hard, while Euclid's algorithm is fast.
(a) If $a=bq+r$ then $\gcd(a,b)=\gcd(b,r)$.
(b) Let $a\ge b\gt0$. Put $r_0=a$, $r_1=b$ and, while $r_i\ne0$, divide: $r_{i-1}=q_ir_i+r_{i+1}$ with $0\le r_{i+1}\lt r_i$. The remainders strictly decrease, so some $r_{n+1}=0$, and then $\gcd(a,b)=r_n$, the last nonzero remainder.
(c) Define $x_0=1,\ y_0=0,\ x_1=0,\ y_1=1$ and $x_{i+1}=x_{i-1}-q_ix_i$, $y_{i+1}=y_{i-1}-q_iy_i$. Then $r_i=ax_i+by_i$ for every $i$; in particular $\gcd(a,b)=ax_n+by_n$.
Proof. (a) If $c$ divides $a$ and $b$ it divides $r=a-bq$; if $c$ divides $b$ and $r$ it divides $a=bq+r$. So the pairs $(a,b)$ and $(b,r)$ have the same common divisors, hence the same greatest one. (b) $r_1\gt r_2\gt\cdots\ge0$ is a strictly decreasing sequence of non-negative integers, so it reaches $0$ after at most $b$ steps. By (a), $\gcd(a,b)=\gcd(r_1,r_2)=\cdots$ $=\gcd(r_n,r_{n+1})$, and $\gcd(r_n,0)=r_n$. (c) Induction: true for $i=0,1$; if $r_{i-1}=ax_{i-1}+by_{i-1}$ and $r_i=ax_i+by_i$, then $r_{i+1}=r_{i-1}-q_ir_i$ $=a(x_{i-1}-q_ix_i)+b(y_{i-1}-q_iy_i)$. ∎
How fast? Each remainder satisfies $r_{i+2}\lt r_i/2$ (if $r_{i+1}\le r_i/2$ this is clear; otherwise $q_{i+1}=1$ and $r_{i+2}=r_i-r_{i+1}\lt r_i/2$), so at most about $2\log_2 b$ steps are needed. The worst case is a pair of consecutive Fibonacci numbers, where every quotient is $1$ (Lamé's theorem, 1844: the number of steps is at most five times the number of decimal digits of $b$).
| $r_i$ | $q_i$ | $x_i$ | $y_i$ |
|---|---|---|---|
| 5390 | — | 1 | 0 |
| 1638 | 3 | 0 | 1 |
| 476 | 3 | 1 | −3 |
| 210 | 2 | −3 | 10 |
| 56 | 3 | 7 | −23 |
| 42 | 1 | −24 | 79 |
| 14 | 3 | 31 | −102 |
Primes and the Fundamental Theorem of Arithmetic
Primes are the multiplicative atoms of $\mathbb{Z}$. The key property that makes them atoms is not the definition ("no proper divisors") but Euclid's lemma for primes: a prime that divides a product divides one of the factors. In a general ring these two properties can come apart (irreducible versus prime elements, §7.2), and unique factorisation then fails.
Proof. The positive divisors of $p$ are $1$ and $p$, so $\gcd(p,a)$ is $p$ (when $p\mid a$) or $1$. If $p\nmid a$, then $\gcd(p,a)=1$ and Theorem 5.19(2) gives $p\mid b$. The general case follows by induction on $k$, applying the case $k=2$ to $a_1\cdot(a_2\cdots a_k)$. Conversely, if $n=ab$ with $1\lt a,b\lt n$, then $n\mid ab$ but $n\nmid a$ and $n\nmid b$. ∎
Proof. Existence (strong induction). $n=2$ is prime. Let $n\gt2$ and assume every integer in $\{2,\dots,n-1\}$ is a product of primes. If $n$ is prime we are done; otherwise $n=ab$ with $1\lt a,b\lt n$, both are products of primes, and so is $n$.
Uniqueness. Suppose some integer has two different factorisations, and let $n$ be the smallest such: $n=p_1p_2\cdots p_k=q_1q_2\cdots q_l$. Since $p_1\mid q_1\cdots q_l$, Theorem 5.21 gives $p_1\mid q_j$ for some $j$; as $q_j$ is prime and $p_1\gt1$, $p_1=q_j$. Cancelling it, $n/p_1=p_2\cdots p_k=q_1\cdots\widehat{q_j}\cdots q_l$. If $n/p_1=1$, both sides are empty products and $k=l=1$. Otherwise $1\lt n/p_1\lt n$, and by minimality these two factorisations of $n/p_1$ agree up to order — hence so do the two factorisations of $n$, a contradiction. ∎
The existence half used only the definition of a prime; the uniqueness half used Euclid's lemma, and through it Bézout and the division algorithm. In $\mathbb{Z}[\sqrt{-5}]$ the analogue of Euclid's lemma fails and so does uniqueness: $6=2\cdot3=(1+\sqrt{-5})(1-\sqrt{-5})$ (§7.2).
- $a\mid b$ if and only if $\alpha_p\le\beta_p$ for every prime $p$; the positive divisors of $a$ are the numbers $\prod p^{\gamma_p}$ with $0\le\gamma_p\le\alpha_p$;
- $\gcd(a,b)=\prod_p p^{\min(\alpha_p,\beta_p)}$ and $\operatorname{lcm}(a,b)=\prod_p p^{\max(\alpha_p,\beta_p)}$;
- $a$ is a perfect $k$-th power if and only if $k\mid\alpha_p$ for every $p$. In particular $\sqrt{n}$ is irrational unless $n$ is a perfect square.
Proof. (1) If $b=ac$, multiplying the factorisations of $a$ and $c$ gives a factorisation of $b$; by uniqueness its exponent of $p$ is $\alpha_p+\gamma_p\ge\alpha_p$. Conversely if $\alpha_p\le\beta_p$ for all $p$, then $b=a\prod p^{\beta_p-\alpha_p}$. (2) By (1) a common divisor has exponents $\le\min(\alpha_p,\beta_p)$, and the displayed number is one; similarly for the lcm. (3) If $a=c^k$ the exponents of $a$ are $k$ times those of $c$; conversely take $c=\prod p^{\alpha_p/k}$. If $\sqrt n=u/v$ in lowest terms then $nv^2=u^2$; comparing exponents, $n$ has all exponents even, i.e. it is a square. ∎
Since $\min+\max=\alpha_p+\beta_p$, part (2) gives a second proof of $\gcd\cdot\operatorname{lcm}=ab$. Counting the divisors in (1) gives $\tau(n)=\prod(\alpha_p+1)$, which we develop in §5.3.
Proof. $v_p(n!)=\sum_{m=1}^{n}v_p(m)$, and $v_p(m)=\#\{k\ge1:\ p^k\mid m\}$. Swapping the order of counting, $v_p(n!)=\sum_{k\ge1}\#\{m\le n:\ p^k\mid m\}$, which is $\sum_{k\ge1}\lfloor n/p^k\rfloor$ because the multiples of $p^k$ up to $n$ are $p^k,2p^k,\dots,\lfloor n/p^k\rfloor p^k$. For the digit form write $n=\sum_j d_jp^j$; then $\lfloor n/p^k\rfloor=\sum_{j\ge k}d_jp^{j-k}$, and summing over $k\ge1$ gives $\sum_j d_j(p^{j}-1)/(p-1)=(n-s_p(n))/(p-1)$. ∎
Proof. (a) Suppose $p_1,\dots,p_k$ were all the primes, and let $N=p_1p_2\cdots p_k+1$. $N\gt1$ has a prime factor $p$ (Theorem 5.22), and $p=p_i$ for some $i$. Then $p\mid N-p_1\cdots p_k=1$, which is impossible.
(b) Suppose $p_1,\dots,p_k$ were all the primes $\equiv3\pmod4$, and put $N=4p_1\cdots p_k-1$. $N$ is odd and $N\equiv3\pmod4$. A product of numbers $\equiv1\pmod4$ is $\equiv1\pmod4$, so not all prime factors of $N$ are $\equiv1\pmod 4$: some prime $q\mid N$ has $q\equiv3\pmod4$, and $q=p_i$ for some $i$. Then $q\mid4p_1\cdots p_k-N=1$, a contradiction. ∎
The same trick does not work for primes $\equiv1\pmod4$ (a product of primes $\equiv3$ can be $\equiv1$); that case needs §5.3 (Exercise II.6 there). Dirichlet's theorem (1837) says that for $\gcd(a,n)=1$ there are infinitely many primes $\equiv a\pmod n$, and the prime number theorem says the number $\pi(x)$ of primes up to $x$ satisfies $\pi(x)\sim x/\log x$. Both are quoted without proof. In the other direction, gaps between primes can be as long as we like: $n!+2,\ n!+3,\ \dots,\ n!+n$ are $n-1$ consecutive composite numbers.
Linear Diophantine Equations
A Diophantine equation is one whose solutions are required to be integers. The linear case $ax+by=c$ is completely solved by Bézout, and its non-negative solutions answer practical questions about making up amounts from given units.
Proof. The values of $ax+by$ are exactly the multiples of $d$ (Theorem 5.18(3)); this is the solvability criterion. If $d\mid c$, scaling a Bézout pair by $c/d$ gives a solution. The displayed pairs are solutions: $a(x_0+\tfrac bdt)+b(y_0-\tfrac adt)=ax_0+by_0=c$. Conversely, if $ax+by=c$, then $a(x-x_0)=-b(y-y_0)$; dividing by $d$, $\tfrac ad(x-x_0)=-\tfrac bd(y-y_0)$. Since $\gcd(\tfrac ad,\tfrac bd)=1$, Euclid's lemma gives $\tfrac bd\mid x-x_0$; write $x-x_0=\tfrac bdt$, and then $y-y_0=-\tfrac adt$. ∎
Geometrically the solutions are the lattice points on the line $ax+by=c$; consecutive ones differ by the vector $\left(\tfrac bd,-\tfrac ad\right)$. On a bounded segment of the line — for instance the part in the first quadrant — there are only finitely many, and we count them by bounding $t$.
Proof. For each integer $n$ there is a unique pair with $n=ax+by$ and $0\le x\le b-1$: by Theorem 5.26 the $x$-values of all solutions form one residue class modulo $b$. Then $n$ is representable if and only if this $y$ is $\ge0$ (any other solution has $x\lt0$ or a smaller $y$).
Let $N=ab-a-b$. For $n=N$ the pair is $x=b-1$, $y=-1$ (check: $a(b-1)-b=N$), so $N$ is not representable. If $n\gt N$ and $0\le x\le b-1$, then $by=n-ax\gt N-a(b-1)=-b$, so $y\gt-1$, i.e. $y\ge0$: every $n\gt N$ is representable. Finally, if $n=ax+by$ with $0\le x\le b-1$, then $N-n=a(b-1-x)+b(-1-y)$ with $0\le b-1-x\le b-1$; exactly one of $y$ and $-1-y$ is $\ge0$. So among the $N+1$ integers $0,1,\dots,N$, the map $n\mapsto N-n$ pairs each representable number with a non-representable one, and exactly $\tfrac{N+1}{2}=\tfrac{(a-1)(b-1)}{2}$ are non-representable. ∎
Congruences and Linear Congruences
Gauss (1801) introduced the notation that turned divisibility into algebra: instead of "$n$ divides $a-b$" we write an equation-like statement and compute with it as with equalities.
Let $n\ge1$. Integers $a,b$ are congruent modulo $n$, written $a\equiv b\pmod n$, if $n\mid a-b$ — equivalently, if $a$ and $b$ leave the same remainder on division by $n$. The residue class of $a$ is $\bar a=\{a+kn:k\in\mathbb{Z}\}$, and $\mathbb{Z}_n=\mathbb{Z}/n\mathbb{Z}=\{\bar0,\bar1,\dots,\overline{n-1}\}$ is the set of the $n$ classes.
A complete residue system modulo $n$ is a set of $n$ integers containing exactly one element of each class, such as $\{0,1,\dots,n-1\}$ or $\{-2,-1,0,1,2\}$ for $n=5$.
- Congruence modulo $n$ is an equivalence relation on $\mathbb{Z}$; its classes are the residue classes.
- If $a\equiv b$ and $c\equiv d\pmod n$, then $a+c\equiv b+d$, $a-c\equiv b-d$ and $ac\equiv bd\pmod n$. Hence $a^k\equiv b^k$ and $f(a)\equiv f(b)\pmod n$ for every polynomial $f$ with integer coefficients.
- Cancellation. $ca\equiv cb\pmod n$ if and only if $a\equiv b\pmod{n/\gcd(c,n)}$. In particular, if $\gcd(c,n)=1$ we may cancel $c$.
- If $a\equiv b\pmod{m_i}$ for $i=1,\dots,k$, then $a\equiv b\pmod{\operatorname{lcm}(m_1,\dots,m_k)}$.
Proof. (1) $n\mid0$; $n\mid a-b\Rightarrow n\mid b-a$; $n\mid a-b$ and $n\mid b-c\Rightarrow n\mid a-c$. (2) $(a+c)-(b+d)=(a-b)+(c-d)$ and $ac-bd=a(c-d)+d(a-b)$ are combinations of multiples of $n$. Induction gives powers, and a polynomial is built from $+$ and $\times$.
(3) Let $g=\gcd(c,n)$, $c=gc'$, $n=gn'$ with $\gcd(c',n')=1$. Then $n\mid c(a-b)$ $\iff gn'\mid gc'(a-b)$ $\iff n'\mid c'(a-b)$ $\iff n'\mid a-b$, the last step by Euclid's lemma. (4) $a-b$ is a common multiple of the $m_i$, hence a multiple of their lcm (Theorem 5.19(6), extended by induction). ∎
Part (2) says that addition and multiplication of classes, $\bar a+\bar b=\overline{a+b}$ and $\bar a\,\bar b=\overline{ab}$, are well defined, so $\mathbb{Z}_n$ is a commutative ring (§7.1). Part (3) is where congruences differ from equations: $2\cdot3\equiv2\cdot8\pmod{10}$ but $3\not\equiv8\pmod{10}$ — we may only conclude $3\equiv8\pmod5$.
Divisibility tests. Since $10\equiv1\pmod9$, a number is congruent to its digit sum mod $9$ (and mod $3$). Since $10\equiv-1\pmod{11}$, it is congruent mod $11$ to its alternating digit sum taken from the units digit. And since $1000\equiv-1\pmod{1001}$ with $1001=7\cdot11\cdot13$, it is congruent mod $7$, $11$ and $13$ to the alternating sum of its three-digit blocks: $31\,415\,926\equiv926-415+31=542$, and $542\equiv3\pmod7$, $542\equiv3\pmod{11}$, $542\equiv9\pmod{13}$.
Proof. $ax\equiv b\pmod n$ means $ax-ny=b$ for some integer $y$ — a linear Diophantine equation, solvable iff $d\mid b$ (Theorem 5.26). Its general solution has $x=x_0+\tfrac ndt$, $t\in\mathbb{Z}$. Two of these, with parameters $t$ and $t'$, are congruent mod $n$ iff $n\mid\tfrac nd(t-t')$ iff $d\mid t-t'$; so they fall into exactly $d$ classes mod $n$, represented by $t=0,\dots,d-1$. For $b=1$ the condition $d\mid1$ is $d=1$, and then the solution is unique. ∎
The Chinese Remainder Theorem
A problem in the Sunzi Suanjing (3rd–5th century) asks for a number leaving remainders $2,3,2$ on division by $3,5,7$. The general principle is that congruences to coprime moduli are independent: any combination of remainders occurs, exactly once in each block of $m_1m_2\cdots m_k$ consecutive integers.
Let $m_1,\dots,m_k\ge1$ be pairwise coprime and $M=m_1m_2\cdots m_k$. For any integers $a_1,\dots,a_k$ the system $$x\equiv a_i\pmod{m_i}\qquad(i=1,\dots,k)$$ has a solution, and any two solutions are congruent modulo $M$. Explicitly, with $M_i=M/m_i$ and $y_i\equiv M_i^{-1}\pmod{m_i}$, $$x\equiv\sum_{i=1}^{k}a_iM_iy_i\pmod M.$$
Ring form. The map $\mathbb{Z}_M\to\mathbb{Z}_{m_1}\times\cdots\times\mathbb{Z}_{m_k}$, $\ \bar x\mapsto(x\bmod m_1,\dots,x\bmod m_k)$, is a bijection that preserves addition and multiplication (a ring isomorphism).
Proof. Existence. $M_i$ is the product of the $m_j$ with $j\ne i$, each coprime to $m_i$, so $\gcd(M_i,m_i)=1$ (Theorem 5.19(4)) and $y_i$ exists (Theorem 5.29). For $j\ne i$, $m_j\mid M_i$, so $a_iM_iy_i\equiv0\pmod{m_j}$. Hence modulo $m_j$ the sum reduces to its $j$-th term, $a_jM_jy_j\equiv a_j\cdot1=a_j\pmod{m_j}$.
Uniqueness. If $x,x'$ both solve the system, every $m_i$ divides $x-x'$, and since the $m_i$ are pairwise coprime their product divides $x-x'$ (Theorem 5.19(3)). Conversely every $x'\equiv x\pmod M$ is again a solution.
Ring form. The map is well defined (each $m_i\mid M$) and preserves $+$ and $\times$ by Theorem 5.28(2). Uniqueness says it is injective; existence says it is surjective. (Or: an injective map between two finite sets with $M$ elements each is bijective.) ∎
Proof. A common solution has the form $x=a+mt$ with $a+mt\equiv b\pmod n$, i.e. $mt\equiv b-a\pmod n$. By Theorem 5.29 this is solvable in $t$ iff $g\mid b-a$, and then $t$ is unique modulo $n/g$; so $x=a+mt$ is unique modulo $mn/g=\operatorname{lcm}(m,n)$. Necessity of the pairwise condition in the general case is clear (a solution satisfies $a_i\equiv x\equiv a_j$ modulo $\gcd(m_i,m_j)$). For sufficiency one combines the congruences one at a time: the solution set of the first two is a single class $x\equiv c\pmod{\ell}$ with $\ell=\operatorname{lcm}(m_1,m_2)$, and checking prime by prime one finds $c\equiv a_3\pmod{\gcd(\ell,m_3)}$ (for each prime $p$, the exponent of $p$ in $\gcd(\ell,m_3)$ is attained in $\gcd(m_1,m_3)$ or in $\gcd(m_2,m_3)$); induct. ∎
Proof. Under the CRT bijection $\bar x\mapsto(x\bmod m,\ x\bmod n)$, $f(x)\equiv0\pmod{mn}$ holds iff $f(x)\equiv0\pmod m$ and $f(x)\equiv0\pmod n$ (Theorem 5.19(3) and Theorem 5.28(2)). So the roots mod $mn$ correspond bijectively to pairs (root mod $m$, root mod $n$). ∎
For instance $x^2\equiv1$ has $2$ roots modulo an odd prime power $p^a$ (Exercise IV.10), $1$ root mod $2$, $2$ mod $4$ and $4$ modulo $2^a$ for $a\ge3$. So modulo $360=2^3\cdot3^2\cdot5$ it has $4\cdot2\cdot2=16$ roots — far more than the "$\pm1$" one might expect.
Fermat's Little Theorem and Wilson's Theorem
Modulo a prime $p$, every nonzero residue is invertible (Theorem 5.29), so $\mathbb{Z}_p$ is a field. Two classical theorems describe its multiplicative structure: the nonzero residues all satisfy $x^{p-1}=1$ (Fermat, 1640), and their product is $-1$ (Wilson's theorem, first proved by Lagrange in 1771). In §5.3 both are subsumed by the theory of primitive roots.
Proof. Suppose $p\nmid a$. The numbers $a,2a,\dots,(p-1)a$ are nonzero mod $p$ (Euclid's lemma) and pairwise incongruent: $ia\equiv ja$ implies $i\equiv j\pmod p$ by cancellation, as $\gcd(a,p)=1$. So they are the residues $1,2,\dots,p-1$ in some order, and multiplying, $$a^{p-1}\,(p-1)!\equiv(p-1)!\pmod p.$$ Since $\gcd((p-1)!,p)=1$ we may cancel $(p-1)!$, giving $a^{p-1}\equiv1$. Multiplying by $a$ gives $a^p\equiv a$, which also holds (as $0\equiv0$) when $p\mid a$. ∎
Second proof of $a^p\equiv a$ (induction on $a\ge0$). For $0\lt k\lt p$, $p$ divides $\binom pk=\frac{p!}{k!(p-k)!}$, because $p$ divides the numerator but not the denominator. Hence $(a+1)^p=\sum_k\binom pka^k\equiv a^p+1\equiv a+1\pmod p$ by the induction hypothesis; negative $a$ follow since $a\equiv a+kp$. The congruence $(x+y)^p\equiv x^p+y^p\pmod p$ — the "freshman's dream" — reappears as the Frobenius map of finite fields (§8.2).
Proof. $p\mid x^2-1=(x-1)(x+1)$, so $p\mid x-1$ or $p\mid x+1$ by Euclid's lemma. A residue $a$ with $a\cdot a\equiv1$ is exactly a root of $x^2\equiv1$. ∎
Proof. Primes. For $p=2$: $1!=1\equiv-1$; for $p=3$: $2!=2\equiv-1$. Let $p\ge5$. Every $a\in\{2,3,\dots,p-2\}$ has an inverse $a'$ mod $p$ in $\{1,\dots,p-1\}$; $a'\ne1$ (else $a\equiv1$), $a'\ne p-1$ (else $a\equiv-1$), and $a'\ne a$ by Theorem 5.34. So the $p-3$ numbers $2,\dots,p-2$ split into pairs $\{a,a'\}$ with $aa'\equiv1$, and their product is $\equiv1$. Hence $(p-1)!\equiv1\cdot1\cdot(p-1)\equiv-1\pmod p$.
Composites. Let $n$ be composite, with a divisor $a$, $1\lt a\lt n$. Then $a\mid(n-1)!$ (it is one of the factors). If $(n-1)!\equiv-1\pmod n$, then $a\mid n\mid(n-1)!+1$, so $a\mid1$ — impossible. For the stronger statement: if $n=ab$ with $1\lt a\lt b\lt n$, both $a$ and $b$ occur in $(n-1)!$, so $n=ab\mid(n-1)!$. Otherwise $n=p^2$ for a prime $p$; if $p\gt2$, then $p$ and $2p$ are distinct factors of $(n-1)!$ ($2p\lt p^2$), so $2p^2\mid(n-1)!$. The remaining case is $n=4$, where $3!=6\equiv2$. ∎
Proof. Pair $k$ with $p-k\equiv-k$ in Wilson's product: $$(p-1)!=\prod_{k=1}^{(p-1)/2}k(p-k)\equiv\prod_{k=1}^{(p-1)/2}(-k^2),$$ $$\prod_{k=1}^{(p-1)/2}(-k^2)=(-1)^{(p-1)/2}\left(\left(\tfrac{p-1}2\right)!\right)^2.$$ If $p\equiv1\pmod4$ then $(p-1)/2$ is even and Wilson gives $\left(\left(\tfrac{p-1}2\right)!\right)^2\equiv-1$. Conversely, if $x^2\equiv-1$ then $p\nmid x$ and by Fermat $1\equiv x^{p-1}=(x^2)^{(p-1)/2}\equiv(-1)^{(p-1)/2}$; as $p\gt2$, $1\not\equiv-1$, so $(p-1)/2$ is even. ∎
For $p=13$: $6!=720=55\cdot13+5$, and $5^2=25\equiv-1\pmod{13}$ ✓. Theorem 5.36 is the first case of the theory of quadratic residues (§5.3), and it is the key step in Fermat's theorem that a prime $p\equiv1\pmod4$ is a sum of two squares.
- $a\mid bc$ does not give $a\mid b$ or $a\mid c$. $6\mid4\cdot9$ but $6\nmid4$, $6\nmid9$. It works when $a$ is prime (Theorem 5.21) or when $\gcd(a,b)=1$ (then $a\mid c$).
- Cancellation needs coprimality. $2\cdot3\equiv2\cdot8\pmod{10}$ but $3\not\equiv8\pmod{10}$; only $3\equiv8\pmod{5}$ follows.
- A linear congruence can have no solution or many. $2x\equiv1\pmod4$ has none; $2x\equiv2\pmod4$ has two ($x\equiv1,3$); $6x\equiv0\pmod{12}$ has six.
- Pairwise coprime, not just coprime. $\gcd(6,10,15)=1$, but $6,10,15$ are not pairwise coprime: $x\equiv0\pmod6$, $x\equiv1\pmod{10}$ is unsolvable, and $\mathbb{Z}_{900}\not\cong\mathbb{Z}_6\times\mathbb{Z}_{10}\times\mathbb{Z}_{15}$ (the right side has no element of additive order $900$).
- $\gcd\cdot\operatorname{lcm}=ab$ is for two numbers only. For $2,2,2$: $\gcd=2$, $\operatorname{lcm}=2$, product $8$.
- The converse of Fermat is false. $2^{340}\equiv1\pmod{341}$ with $341=11\cdot31$; the Carmichael number $561$ fools every coprime base.
- $a^{p-1}\equiv1$ needs $p\nmid a$. $7^{6}\equiv0\pmod7$. The version $a^p\equiv a$ holds for every $a$.
- Reduce exponents mod $p-1$, not mod $p$. $2^{13}\equiv2\pmod{13}$, not $2^0=1$; but $2^{12}\equiv1$.
- More than two square roots of $1$ for composite moduli. $x^2\equiv1\pmod8$ has four roots $1,3,5,7$; $x^2\equiv1\pmod{15}$ has $1,4,11,14$. Theorem 5.34 is special to primes (and odd prime powers).
- Wilson's congruence fails at $n=4$ in an unexpected way. $3!=6\equiv2\pmod4$ — neither $-1$ nor $0$.
- Patterns are not proofs. $n^2+n+41$ is prime for $0\le n\le39$ but not for $n=40$; $2^p-1$ is prime for $p=2,3,5,7$ but not for $p=11$.
- The exponent of $p$ in $n!$ is not $\lfloor n/p\rfloor$. $v_5(100!)=20+4=24$, not $20$: multiples of $25$ contribute twice.
Exercises
- 1 Use Euclid's algorithm to find $\gcd(2310,1001)$ and integers $x,y$ with $2310x+1001y=\gcd(2310,1001)$.
- 2 Find the quotient and remainder of $-83$ on division by $9$.
- 3 Prove that $\gcd(2n+1,3n+1)=1$ for every integer $n$.
- 4 Show that $\gcd(n^2+1,n+1)$ is $1$ or $2$, and decide for which $n$ it equals $2$.
- 5 Find all pairs of positive integers $a\le b$ with $\gcd(a,b)=12$ and $\operatorname{lcm}(a,b)=360$.
- 6 Prove that if $\gcd(a,b)=1$ then $\gcd(a+b,ab)=1$ and $\gcd(a+b,a-b)\in\{1,2\}$.
- 7 Prove that $\gcd(2^m-1,2^n-1)=2^{\gcd(m,n)}-1$ for $m,n\ge1$, and evaluate $\gcd(2^{12}-1,2^{18}-1)$.
- 8 Run Euclid's algorithm on $(89,55)$. How many divisions are needed? Prove that consecutive Fibonacci numbers are always coprime.
- 1 Find the exponent of $7$ in $1000!$, and the number of trailing zeros of $125!$ and of $2026!$.
- 2 Find the largest $k$ such that $6^k$ divides $40!$.
- 3 Prove that if $2^n+1$ is prime ($n\ge1$), then $n$ is a power of $2$.
- 4 Prove that there are infinitely many primes $p\equiv2\pmod3$.
- 5 Prove that $n^4+4$ is composite for every integer $n\gt1$.
- 6 Prove that every prime $p$ with $n\lt p\le2n$ divides $\binom{2n}{n}$, and that $\binom{2n}n\lt4^n$. (These facts are the start of Erdős's proof of Bertrand's postulate.)
- 7 Show that $\log_{10}2$ is irrational, using unique factorisation.
- 8 Prove or disprove: if $a^3\mid b^2$ then $a\mid b$.
- 1 Find all integer solutions of $56x+72y=40$.
- 2 Find all solutions of $7x+11y=200$ in positive integers.
- 3 Show that $12x+18y=25$ has no integer solution, and that $12x+18y+25z=1$ does.
- 4 Stamps come in values $5$ and $8$. Find the largest postage that cannot be paid exactly and the number of postages (in whole units) that cannot be paid.
- 5 Solve $15x\equiv25\pmod{35}$.
- 6 Find the inverse of $17$ modulo $101$.
- 7 Without dividing, find $31\,415\,926\bmod 9$ and decide whether $123\,456\,789$ is divisible by $11$.
- 8 Prove that $30\mid n^5-n$ and $2730\mid n^{13}-n$ for every integer $n$.
- 9 For which $n\ge2$ does $1+2+\cdots+(n-1)\equiv0\pmod n$?
- 1 Solve $x\equiv1\pmod5$, $x\equiv2\pmod7$, $x\equiv3\pmod9$.
- 2 Solve $x\equiv7\pmod{10}$, $x\equiv12\pmod{15}$, and show that $x\equiv7\pmod{10}$, $x\equiv13\pmod{15}$ has no solution.
- 3 (Modelling.) A satellite is above ground station A at hours $4,13,22,\dots$ (every $9$ hours) and above station B at hours $6,20,34,\dots$ (every $14$ hours), counting from hour $0$. At which hours is it above a station in both lists? Give the first one.
- 4 How many solutions does $x^2\equiv1\pmod{360}$ have?
- 5 Find $2^{1000}\bmod13$ and $2^{100}\bmod77$.
- 6 Find $16!\bmod19$ and $28!\bmod31$.
- 7 Show that $561=3\cdot11\cdot17$ satisfies $a^{560}\equiv1\pmod{561}$ for every $a$ coprime to $561$.
- 8 Let $p$ be an odd prime. Prove that $S=1^{p-1}+2^{p-1}+\cdots+(p-1)^{p-1}$ satisfies $S\equiv-1\pmod p$.
- 9 Prove that if $p$ is prime and $k\ge1$, then $(a+b)^{p^k}\equiv a^{p^k}+b^{p^k}\pmod p$.
- 10 Show that $x^2\equiv1\pmod{p^a}$ has exactly two solutions when $p$ is an odd prime, and exactly four modulo $2^a$ when $a\ge3$.
E1. CSIR Part B The number of integers $x\in\{0,1,\dots,83\}$ satisfying $24x\equiv36\pmod{84}$ is (A) $0$; (B) $6$; (C) $12$; (D) $24$.
E2. CSIR Part B GATE MA The remainder when $7^{222}$ is divided by $55$ is (A) $4$; (B) $14$; (C) $39$; (D) $49$.
E3. CSIR Part B The remainder of $28!$ on division by $31$ is (A) $1$; (B) $15$; (C) $16$; (D) $30$.
E4. CSIR Part C Let $a,b,c$ be nonzero integers. Which of the following statements are true? (One or more options may be correct.) (A) $\gcd(a+b,a-b)$ is either $\gcd(a,b)$ or $2\gcd(a,b)$. (B) If $a\mid bc$ then $a\mid b$ or $a\mid c$. (C) $\gcd(a^2,b^2)=\gcd(a,b)^2$. (D) $\gcd(a,b,c)\cdot\operatorname{lcm}(a,b,c)=|abc|$.
E5. CSIR Part C Which of the following are true? (One or more options may be correct.) (A) The system $x\equiv3\pmod6$, $x\equiv5\pmod8$ is solvable. (B) The system $x\equiv1\pmod4$, $x\equiv2\pmod6$ is solvable. (C) The system $x\equiv2\pmod9$, $x\equiv5\pmod{12}$, $x\equiv8\pmod{15}$ has a unique solution modulo $180$. (D) $x^2\equiv1\pmod{15}$ has exactly two solutions modulo $15$.
E6. CSIR Part C GATE MA Which of the following statements are true? (One or more options may be correct.) (A) For every prime $p$ and every integer $a$, $p\mid a^p-a$. (B) If $n\gt1$ and $2^{n-1}\equiv1\pmod n$, then $n$ is prime. (C) If $n\gt1$ and $(n-1)!\equiv-1\pmod n$, then $n$ is prime. (D) $n^{13}-n$ is divisible by $2730$ for every integer $n$.
Suggested plan — 3 lectures × 60 min.
- Division, gcd, Euclid. Well-ordering and the division algorithm (Theorem 5.17) — insist on $0\le r\lt b$ for negative $a$. Bézout via "least positive combination" (Theorem 5.18), stressing that the proof is the PID argument of §7.2. Project Interactive 1 on $46\times18$ and then $55\times34$; let the class predict the gcd from the picture. Example 1 on the board with the table. Theorem 5.19 (Euclid's lemma) at the end.
- Primes, FTA, Diophantine equations. Theorems 5.21–5.22 with the "minimal counterexample" uniqueness proof; mention $\mathbb{Z}[\sqrt{-5}]$. Legendre's formula (Example 3 — students love trailing zeros). Theorem 5.26 and Example 4; draw the lattice points on the line. State Theorem 5.27 and do the $5,8$ stamps by listing.
- Congruences, CRT, Fermat, Wilson. Theorem 5.28 with the cancellation warning, Theorem 5.29 and Example 5; the CRT with Interactive 2 ($3\times5$, then $4\times6$ — ask why the empty cells are exactly those with $a-b$ odd); Example 6. Fermat (permutation proof), Wilson (pairing inverses), Example 7, Exam-corner E2 and E6 live.
Discussion questions. (1) Why does the proof of Bézout's identity not tell us how to find $x$ and $y$, and how does Euclid's algorithm fill that gap? (2) In the CRT grid for $m=4$, $n=6$, which cells are reached and why is the count $\operatorname{lcm}(4,6)=12$? (3) Fermat's theorem gives a quick test that can prove a number composite without finding a factor. How is that possible?
Misconceptions to watch for. Negative remainders; cancelling a common factor in a congruence; "$a\mid bc\Rightarrow a\mid b$ or $a\mid c$"; thinking a linear congruence always has exactly one solution; using the CRT with non-coprime moduli; reducing an exponent modulo $p$ instead of $p-1$; believing $a^{n-1}\equiv1\pmod n$ proves $n$ prime; counting only $\pm1$ as square roots of $1$ modulo a composite.
Suggested homework. I(1, 4, 5, 7), II(1, 2, 4, 5), III(1, 2, 5, 8), IV(1, 3, 4, 6, 7); Exam corner E1, E4, E5.
Research question. How often does the Fermat test lie? If we declare $n$ "probably prime" whenever $2^{n-1}\equiv1\pmod n$, how many composite numbers slip through, and can a cleverer test close the loophole?
Why it matters. Every time a phone opens a secure connection, software somewhere has generated large random primes for RSA or Diffie–Hellman keys. Proving primality of a 300-digit number by trial division is hopeless, so cryptographic libraries in use around the world run fast probabilistic tests built on Fermat's little theorem and Theorem 5.34. Understanding their failure modes — pseudoprimes and Carmichael numbers — is what makes those tests trustworthy.
What to do.
- Write a function computing $a^k\bmod n$ by repeated squaring (or use Python's built-in three-argument
pow). Check it against Example 7. - List all odd composite $n\lt10^5$ with $2^{n-1}\equiv1\pmod n$ (base-$2$ pseudoprimes). How many are there, compared with the $9591$ odd primes below $10^5$?
- Among them, find those that also pass base $3$, and those that pass for every base coprime to $n$ (Carmichael numbers). Verify Korselt's criterion on each Carmichael number you find.
- Implement the Miller–Rabin refinement: write $n-1=2^st$ with $t$ odd and declare $n$ composite if $a^t\not\equiv1$ and $a^{2^jt}\not\equiv-1$ for all $j\lt s$. Explain, using Theorem 5.34, why a prime always passes. Does $561$ pass for $a=2$?
Tools: Python (integers of any size, pow(a, k, n)), or any language with big-integer support; a spreadsheet for the counts.
Hand in: A one-page note with your counts, the list of Carmichael numbers below $10^5$, and a short explanation of why Miller–Rabin catches $561$.
Going further. Read about the 1994 proof by Alford, Granville and Pomerance that there are infinitely many Carmichael numbers, and about the AKS algorithm (2002), which decides primality deterministically in polynomial time.
🧪 Self-check quiz
Q1. For integers $a,b$ not both zero, $\gcd(a,b)=1$ holds if and only if
Q2. How many solutions modulo $15$ does $6x\equiv9\pmod{15}$ have?
Q3. The remainder of $5^{38}$ on division by $13$ is
Q4. The system $x\equiv a\pmod6$, $x\equiv b\pmod{10}$ is solvable exactly when
Q5. For which integers $n\gt1$ is $(n-1)!$ not divisible by $n$?