Chapter 5 · Combinatorics and Number Theory

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.

📘 Definition 5.7 — Divisibility and primes

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.

📐 Theorem 5.16 — Basic properties of divisibility
For all integers $a,b,c,x,y$:
  1. $a\mid b$ and $b\mid c$ $\Rightarrow$ $a\mid c$ (transitivity);
  2. $a\mid b$ and $a\mid c$ $\Rightarrow$ $a\mid bx+cy$ (divisors of two numbers divide every integer combination);
  3. $a\mid b$ and $b\ne0$ $\Rightarrow$ $|a|\le|b|$;
  4. $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|$. ∎

📐 Theorem 5.17 — The division algorithm
Let $a,b\in\mathbb{Z}$ with $b\gt0$. There are unique integers $q$ (the quotient) and $r$ (the remainder) such that $$a=bq+r,\qquad 0\le r\lt b.$$ We write $r=a\bmod b$. Note that $b\mid a$ if and only if $a\bmod b=0$.

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$.

📘 Definition 5.8 — gcd, lcm and coprime integers

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.

📐 Theorem 5.18 — Bézout's identity
Let $a,b$ be integers, not both $0$, and let $d$ be the least positive element of the set $L=\{ax+by:\ x,y\in\mathbb{Z}\}$. Then
  1. $d=\gcd(a,b)$; in particular there are integers $x,y$ with $ax+by=\gcd(a,b)$;
  2. every common divisor of $a$ and $b$ divides $\gcd(a,b)$;
  3. $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).

📐 Theorem 5.19 — Consequences of Bézout
Let $a,b,c$ be integers.
  1. Coprimality criterion. $\gcd(a,b)=1$ if and only if $ax+by=1$ for some integers $x,y$.
  2. Euclid's lemma. If $a\mid bc$ and $\gcd(a,b)=1$, then $a\mid c$.
  3. 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$.
  4. If $\gcd(a,b)=1$ and $\gcd(a,c)=1$, then $\gcd(a,bc)=1$.
  5. If $d=\gcd(a,b)\ne0$ then $\gcd(a/d,\,b/d)=1$; and $\gcd(ma,mb)=|m|\gcd(a,b)$.
  6. 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.

📐 Theorem 5.20 — The Euclidean algorithm and its extension

(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$).

🧭 Strategy — Extended Euclid as a table
Write the rows $(r_i,\ q_i,\ x_i,\ y_i)$, starting with $(a,\ -,\ 1,\ 0)$ and $(b,\ q_1,\ 0,\ 1)$. Each new row is "the row two above minus $q$ times the row above", in every column. Stop when the remainder is $0$; the previous row gives $\gcd(a,b)=ax+by$. Always check the final identity by multiplying out — sign slips are the commonest error.
✏️ Example 1 — $\gcd(5390,1638)$, Bézout coefficients and the lcm
Find $d=\gcd(5390,1638)$, integers $x,y$ with $5390x+1638y=d$, all such pairs $(x,y)$, and $\operatorname{lcm}(5390,1638)$.
Divisions $5390=3\cdot1638+476$; $\ 1638=3\cdot476+210$; $\ 476=2\cdot210+56$; $\ 210=3\cdot56+42$; $\ 56=1\cdot42+14$; $\ 42=3\cdot14+0$. The last nonzero remainder is $d=14$.
Table
$r_i$$q_i$$x_i$$y_i$
5390—10
1638301
47631−3
2102−310
5637−23
421−2479
14331−102
(Row $476$: $1-3\cdot0=1$, $0-3\cdot1=-3$; row $210$: $0-3\cdot1=-3$, $1-3(-3)=10$; and so on. The $q$ in each row is the quotient used to produce the next remainder.)
Check $5390\cdot31-1638\cdot102=167090-167076=14$. ✓
All pairs If $5390x+1638y=14$, subtract the particular identity: $5390(x-31)=-1638(y+102)$. Divide by $14$: $385(x-31)=-117(y+102)$, and $\gcd(385,117)=1$ (Theorem 5.19(5)). By Euclid's lemma $117\mid x-31$, so $x=31+117t$ and then $y=-102-385t$, $t\in\mathbb{Z}$.
lcm $\operatorname{lcm}(5390,1638)=\dfrac{5390\cdot1638}{14}=385\cdot1638=630630$. (Factorised: $5390=2\cdot5\cdot7^2\cdot11$, $1638=2\cdot3^2\cdot7\cdot13$, and $630630=2\cdot3^2\cdot5\cdot7^2\cdot11\cdot13$.)
Interactive 1 — Euclid's Algorithm as Cutting Squares

An $a\times b$ rectangle is cut into the largest possible squares: $q_1$ squares of side $b$, leaving a $r\times b$ strip, which is cut the same way, and so on. Each cut is one division $r_{i-1}=q_ir_i+r_{i+1}$. The smallest square tiles every rectangle before it, so its side divides both $a$ and $b$ — it is $\gcd(a,b)$. Press Play to cut step by step; the table on the right is the algorithm, and the last line is Bézout's identity read off from the extended table.

a, b—
step—
division—
gcd(a, b)—
Bézout—
lcm(a, b)—

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.

📐 Theorem 5.21 — Euclid's lemma for primes
Let $p$ be prime. If $p\mid ab$ then $p\mid a$ or $p\mid b$. More generally, if $p\mid a_1a_2\cdots a_k$ then $p\mid a_i$ for some $i$. Conversely, an integer $n\gt1$ with this property is prime.

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$. ∎

📐 Theorem 5.22 — Fundamental theorem of arithmetic
Every integer $n\gt1$ can be written as a product of primes, $n=p_1p_2\cdots p_k$, and this factorisation is unique apart from the order of the factors. Grouping equal primes, $n=p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$ with $p_1\lt p_2\lt\cdots\lt p_r$ and $a_i\ge1$ — the canonical factorisation.

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).

📐 Theorem 5.23 — Reading arithmetic off factorisations
Let $a=\prod_p p^{\alpha_p}$ and $b=\prod_p p^{\beta_p}$ be positive integers (products over all primes, almost all exponents $0$). Then
  1. $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$;
  2. $\gcd(a,b)=\prod_p p^{\min(\alpha_p,\beta_p)}$ and $\operatorname{lcm}(a,b)=\prod_p p^{\max(\alpha_p,\beta_p)}$;
  3. $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.

📐 Theorem 5.24 — Legendre's formula for the prime exponents of $n!$
For a prime $p$ and $n\ge1$, the exponent of $p$ in $n!$ is $$v_p(n!)=\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^2}\right\rfloor+\left\lfloor\frac{n}{p^3}\right\rfloor+\cdots$$ (a finite sum: the terms vanish once $p^k\gt n$). Equivalently $v_p(n!)=\dfrac{n-s_p(n)}{p-1}$, where $s_p(n)$ is the sum of the base-$p$ digits of $n$.

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)$. ∎

📐 Theorem 5.25 — There are infinitely many primes (Euclid)
(a) The set of primes is infinite. (b) There are infinitely many primes $p\equiv3\pmod4$, i.e. of the form $4k+3$.

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.

✏️ Example 2 — Primes: prove or disprove
Prove or disprove: (a) $n^2+n+41$ is prime for every $n\ge0$; (b) if $2^n-1$ is prime, then $n$ is prime; (c) if $n$ is prime, then $2^n-1$ is prime; (d) if $p$ is prime and $p\mid a^k$ for some $k\ge1$, then $p^k\mid a^k$; (e) if $a^2\mid b^2$ then $a\mid b$.
(a) False It is prime for $n=0,1,\dots,39$ (Euler's famous polynomial), but $n=40$ gives $40^2+40+41=40\cdot41+41=41^2$. (Also $n=41$: $41\cdot43$.) No non-constant integer polynomial takes only prime values — checking many cases proves nothing.
(b) True If $n=rs$ with $1\lt r,s\lt n$, then $x-1\mid x^s-1$ with $x=2^r$ gives $2^r-1\mid2^{rs}-1$, and $1\lt2^r-1\lt2^n-1$. So $2^n-1$ is composite. (Also $n=1$ gives $2^1-1=1$, not prime.)
(c) False $n=11$: $2^{11}-1=2047=23\cdot89$. Primes of the form $2^p-1$ are Mersenne primes; only about fifty are known.
(d) True By Theorem 5.21, $p\mid a$; then $a=pc$ and $a^k=p^kc^k$.
(e) True For $a,b\ne0$, by Theorem 5.23(1) $2\alpha_p\le2\beta_p$ for every $p$, i.e. $\alpha_p\le\beta_p$, so $a\mid b$. (If $b=0$ it is trivial, and $a^2\mid b^2$ with $a=0$ forces $b=0$.) Without unique factorisation one would argue: with $d=\gcd(a,b)$, $a=da'$, $b=db'$, $a'^2\mid b'^2$ and $\gcd(a'^2,b'^2)=1$ (Theorem 5.19(4)), so $a'=\pm1$.
✏️ Example 3 — Legendre's formula in action
(a) How many zeros does $1000!$ end with? (b) Find the largest $k$ with $12^k\mid50!$. (c) Find the exponent of $2$ in $\binom{100}{50}$.
(a) Trailing zeros count the factors $10=2\cdot5$, and fives are scarcer than twos, so the answer is $v_5(1000!)=200+40+8+1=249$.
(b) $12^k=2^{2k}3^k$. $v_2(50!)=25+12+6+3+1=47$ and $v_3(50!)=16+5+1=22$. We need $2k\le47$ and $k\le22$, so $k=22$. (The limiting prime is $3$, not $2$ — always check every prime of the base.)
(c) $\binom{100}{50}=\dfrac{100!}{50!\,50!}$, so $v_2=v_2(100!)-2v_2(50!)$. $v_2(100!)=50+25+12+6+3+1=97$, so $v_2=97-94=3$.
Check Digit form: $50=110010_2$ has $s_2=3$, so $v_2(50!)=50-3=47$ ✓; $100=1100100_2$, $v_2(100!)=100-3=97$ ✓. (Kummer's theorem: $v_p\binom{m+n}{m}$ equals the number of carries when adding $m$ and $n$ in base $p$ — adding $110010+110010$ produces $3$ carries.)

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.

📐 Theorem 5.26 — Solving $ax+by=c$
Let $a,b$ be nonzero integers and $d=\gcd(a,b)$. The equation $ax+by=c$ has an integer solution if and only if $d\mid c$. If $(x_0,y_0)$ is one solution, then all solutions are $$x=x_0+\frac{b}{d}\,t,\qquad y=y_0-\frac{a}{d}\,t,\qquad t\in\mathbb{Z}.$$

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$.

📐 Theorem 5.27 — Two coin denominations (Sylvester, 1884)
Let $a,b\ge2$ be coprime. An integer $n$ is representable if $n=ax+by$ with integers $x,y\ge0$. Then the largest non-representable integer is $ab-a-b$, and exactly $\tfrac{(a-1)(b-1)}{2}$ non-negative integers are non-representable.

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. ∎

✏️ Example 4 — Shipping 1000 kg in two box sizes (modelling)
A depot ships powder in sealed boxes holding exactly $13\,\text{kg}$ or $21\,\text{kg}$. (a) In how many ways can exactly $1000\,\text{kg}$ be shipped in full boxes? Which way uses the fewest boxes? (b) Which is the largest load that cannot be shipped in full boxes at all, and how many loads (in whole kg) are impossible?
Bézout We need $13x+21y=1000$ with $x,y\ge0$. Euclid on $21,13$: $21=13+8$, $13=8+5$, $8=5+3$, $5=3+2$, $3=2+1$ (consecutive Fibonacci numbers — every quotient is $1$). Back-substituting (or by the table) $13\cdot(-8)+21\cdot5=-104+105=1$.
General solution Multiply by $1000$: $(x_0,y_0)=(-8000,5000)$. By Theorem 5.26 ($d=1$), $x=-8000+21t$, $y=5000-13t$.
Bounds $x\ge0\iff t\ge8000/21\approx380.95\iff t\ge381$; $\ y\ge0\iff t\le5000/13\approx384.6\iff t\le384$. So $t=381,382,383,384$: 4 ways, $(x,y)=(1,47),(22,34),(43,21),(64,8)$. Check: $13+987=1000$, $286+714$, $559+441$, $832+168$ ✓.
Fewest boxes $x+y=(-8000+21t)+(5000-13t)=8t-3000$, which is $48,56,64,72$ for $t=381,\dots,384$. Each step $t\to t+1$ swaps $13$ boxes of $21\,\text{kg}$ for $21$ boxes of $13\,\text{kg}$, adding $8$ boxes, so the fewest is $(1,47)$: $1$ small and $47$ large boxes, $48$ boxes in all.
(b) By Theorem 5.27 the largest impossible load is $13\cdot21-13-21=239\,\text{kg}$, and there are $\tfrac{12\cdot20}{2}=120$ impossible whole-kg loads (counting from $1$ kg; $0$ is trivially possible).

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.

📘 Definition 5.9 — Congruence modulo $n$

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$.

📐 Theorem 5.28 — Arithmetic of congruences
Fix $n\ge1$.
  1. Congruence modulo $n$ is an equivalence relation on $\mathbb{Z}$; its classes are the residue classes.
  2. 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.
  3. 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$.
  4. 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}$.

📐 Theorem 5.29 — Linear congruences
Let $n\ge1$ and $d=\gcd(a,n)$. The congruence $ax\equiv b\pmod n$ has a solution if and only if $d\mid b$, and then it has exactly $d$ solutions modulo $n$: if $x_0$ is one of them, they are $$x\equiv x_0+k\,\frac nd\pmod n,\qquad k=0,1,\dots,d-1.$$ In particular $a$ has a multiplicative inverse modulo $n$ (some $a'$ with $aa'\equiv1$) if and only if $\gcd(a,n)=1$, and the inverse is unique modulo $n$.

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. ∎

🧭 Strategy — Solving $ax\equiv b\pmod n$
(1) Compute $d=\gcd(a,n)$. If $d\nmid b$: no solution. (2) Otherwise divide everything by $d$: $a'x\equiv b'\pmod{n'}$ with $\gcd(a',n')=1$ (Theorem 5.28(3)). (3) Find $a'^{-1}\bmod n'$ by extended Euclid (or by inspection for small $n'$), and $x_0\equiv a'^{-1}b'\pmod{n'}$. (4) List $x_0,\ x_0+n',\ \dots,\ x_0+(d-1)n'$ modulo $n$. (5) Check one solution in the original congruence.
✏️ Example 5 — Solve $42x\equiv90\pmod{156}$
Find all solutions modulo $156$. Then decide whether $42x\equiv91\pmod{156}$ is solvable.
gcd $156=3\cdot42+30$, $42=30+12$, $30=2\cdot12+6$, $12=2\cdot6$: $d=\gcd(42,156)=6$, and $6\mid90$. So there are exactly $6$ solutions modulo $156$.
Reduce Divide by $6$: $7x\equiv15\pmod{26}$. The inverse of $7$ mod $26$: $7\cdot15=105=4\cdot26+1$, so $7^{-1}\equiv15$. Hence $x\equiv15\cdot15=225\equiv225-208=17\pmod{26}$.
List Modulo $156$: $x\equiv17,\ 43,\ 69,\ 95,\ 121,\ 147$.
Check $42\cdot17=714=4\cdot156+90$ ✓. And $42x\equiv91$ has no solution because $6\nmid91$. (Directly: $42x-156y$ is always even, while $91$ is odd.)

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.

📐 Theorem 5.30 — Chinese Remainder Theorem

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.) ∎

📐 Theorem 5.31 — Two congruences with non-coprime moduli
Let $m,n\ge1$ and $g=\gcd(m,n)$. The system $x\equiv a\pmod m$, $x\equiv b\pmod n$ is solvable if and only if $a\equiv b\pmod g$, and then the solution is unique modulo $\operatorname{lcm}(m,n)$. A system of several congruences $x\equiv a_i\pmod{m_i}$ is solvable if and only if $a_i\equiv a_j\pmod{\gcd(m_i,m_j)}$ for every pair $i,j$.

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. ∎

📐 Theorem 5.32 — Counting roots via the CRT
Let $f$ be a polynomial with integer coefficients and $N_f(n)$ the number of solutions of $f(x)\equiv0\pmod n$ in $\mathbb{Z}_n$. If $\gcd(m,n)=1$ then $N_f(mn)=N_f(m)\,N_f(n)$. Hence $N_f(n)=\prod_{p^a\,\|\,n}N_f(p^a)$, the product over the prime powers exactly dividing $n$.

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.

✏️ Example 6 — Two systems of congruences
(a) Solve $x\equiv3\pmod4$, $x\equiv4\pmod9$, $x\equiv6\pmod{11}$. (b) Solve $x\equiv5\pmod{12}$, $x\equiv11\pmod{18}$. (c) Is $x\equiv5\pmod{12}$, $x\equiv8\pmod{18}$ solvable?
(a) Setup $4,9,11$ are pairwise coprime, $M=396$, $M_1=99$, $M_2=44$, $M_3=36$.
Inverses $99\equiv3\pmod4$ and $3\cdot3=9\equiv1$: $y_1=3$. $\ 44\equiv8\equiv-1\pmod9$: $y_2=8$. $\ 36\equiv3\pmod{11}$ and $3\cdot4=12\equiv1$: $y_3=4$.
Combine $x\equiv3\cdot99\cdot3+4\cdot44\cdot8+6\cdot36\cdot4=891+1408+864=3163\equiv3163-7\cdot396=391\pmod{396}$. Check: $391=4\cdot97+3=9\cdot43+4=11\cdot35+6$ ✓.
(b) Substitution $\gcd(12,18)=6$ and $11-5=6\equiv0\pmod6$, so a solution exists, unique mod $\operatorname{lcm}=36$. Put $x=5+12t$: $12t\equiv6\pmod{18}$, i.e. $2t\equiv1\pmod3$, $t\equiv2\pmod3$. So $x=5+24=29$: $x\equiv29\pmod{36}$. Check: $29=12\cdot2+5=18+11$ ✓.
(c) No $8-5=3$ is not divisible by $\gcd(12,18)=6$. Concretely, $x\equiv5\pmod{12}$ makes $x$ odd while $x\equiv8\pmod{18}$ makes $x$ even.
Interactive 2 — The Chinese Remainder Theorem as a Grid Walk

Column $a$ is the remainder $x\bmod m$, row $b$ is $x\bmod n$. The integers $x=0,1,2,\dots$ are written into cell $(a,b)$ one after another — each step moves one column right and one row down, wrapping round. For coprime $m,n$ the walk fills every cell exactly once before returning to $0$: that is the CRT. For $\gcd(m,n)\gt1$ it returns after only $\operatorname{lcm}(m,n)$ steps and the empty cells are the unsolvable systems. Click a cell to solve its system.

x—
(x mod m, x mod n)—
cells filled—
gcd, lcm—
clicked systemclick a cell

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.

📐 Theorem 5.33 — Fermat's little theorem
Let $p$ be prime. If $p\nmid a$ then $a^{p-1}\equiv1\pmod p$. For every integer $a$, $a^p\equiv a\pmod p$.

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).

🧭 Strategy — Computing $a^k\bmod n$
(1) Reduce the base: replace $a$ by $a\bmod n$ (or by a small negative representative such as $-1$). (2) If $n=p$ is prime and $p\nmid a$, reduce the exponent modulo $p-1$ (not modulo $p$!). For composite $n$, split $n$ into prime powers, work modulo each, and recombine with the CRT; §5.3 gives Euler's theorem for prime powers. (3) For what remains, use repeated squaring: compute $a^2,a^4,a^8,\dots$ and multiply those matching the binary digits of $k$. (4) Look for a small power that is $\pm1$ — it shortens everything.
📐 Theorem 5.34 — Square roots of $1$ modulo a prime
If $p$ is prime and $x^2\equiv1\pmod p$, then $x\equiv1$ or $x\equiv-1\pmod p$. Consequently, for $p\ge3$ the only residues equal to their own inverse are $\pm1$.

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$. ∎

📐 Theorem 5.35 — Wilson's theorem and its converse
An integer $n\ge2$ is prime if and only if $(n-1)!\equiv-1\pmod n$. Moreover, if $n\gt4$ is composite then $(n-1)!\equiv0\pmod n$; and $3!\equiv2\pmod4$.

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$. ∎

📐 Theorem 5.36 — When is $-1$ a square modulo $p$?
Let $p$ be an odd prime. The congruence $x^2\equiv-1\pmod p$ is solvable if and only if $p\equiv1\pmod4$; in that case $x=\left(\frac{p-1}{2}\right)!$ is a solution.

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.

✏️ Example 7 — Fermat and Wilson at work
(a) Find $3^{2026}\bmod17$. (b) Find $97!\bmod101$. (c) Show that $2^{340}\equiv1\pmod{341}$, although $341$ is not prime. What does this say about the converse of Fermat's theorem?
(a) $17\nmid3$, so $3^{16}\equiv1\pmod{17}$ and the exponent reduces mod $16$: $2026=16\cdot126+10$, so $3^{2026}\equiv3^{10}$. Repeated squaring: $3^2=9$, $3^4=81\equiv13\equiv-4$, $3^8\equiv16\equiv-1$. Hence $3^{10}=3^8\cdot3^2\equiv-9\equiv8\pmod{17}$.
(b) Wilson: $100!\equiv-1\pmod{101}$ ($101$ is prime). Write $100!=100\cdot99\cdot98\cdot97!$ with $100\equiv-1$, $99\equiv-2$, $98\equiv-3$: $(-1)(-2)(-3)\,97!=-6\cdot97!\equiv-1$, so $6\cdot97!\equiv1$ and $97!\equiv6^{-1}\pmod{101}$. Since $6\cdot17=102\equiv1$, $\ 97!\equiv17\pmod{101}$.
(c) $341=11\cdot31$ and $2^{10}=1024=3\cdot341+1$, so $2^{10}\equiv1\pmod{341}$ and $2^{340}=(2^{10})^{34}\equiv1$. Thus $a^{n-1}\equiv1\pmod n$ does not imply that $n$ is prime: $341$ is the smallest pseudoprime to base $2$.
Moral Fermat's theorem gives a fast compositeness test (if $a^{n-1}\not\equiv1$, $n$ is certainly composite: e.g. $3^{340}\equiv56\pmod{341}$, which exposes $341$), but not a primality proof. Worse, there are composite $n$, the Carmichael numbers such as $561=3\cdot11\cdot17$, with $a^{n-1}\equiv1$ for every $a$ coprime to $n$ (Exercise IV.7).
⚠️ Counterexamples and pitfalls
  1. $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$).
  2. Cancellation needs coprimality. $2\cdot3\equiv2\cdot8\pmod{10}$ but $3\not\equiv8\pmod{10}$; only $3\equiv8\pmod{5}$ follows.
  3. 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.
  4. 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$).
  5. $\gcd\cdot\operatorname{lcm}=ab$ is for two numbers only. For $2,2,2$: $\gcd=2$, $\operatorname{lcm}=2$, product $8$.
  6. The converse of Fermat is false. $2^{340}\equiv1\pmod{341}$ with $341=11\cdot31$; the Carmichael number $561$ fools every coprime base.
  7. $a^{p-1}\equiv1$ needs $p\nmid a$. $7^{6}\equiv0\pmod7$. The version $a^p\equiv a$ holds for every $a$.
  8. Reduce exponents mod $p-1$, not mod $p$. $2^{13}\equiv2\pmod{13}$, not $2^0=1$; but $2^{12}\equiv1$.
  9. 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).
  10. Wilson's congruence fails at $n=4$ in an unexpected way. $3!=6\equiv2\pmod4$ — neither $-1$ nor $0$.
  11. 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$.
  12. 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

I
Divisibility, gcd and Euclid's algorithm.
  • 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 $2310=2\cdot1001+308$, $1001=3\cdot308+77$, $308=4\cdot77$. So $\gcd=77$. Back-substitute: $77=1001-3\cdot308=1001-3(2310-2\cdot1001)=7\cdot1001-3\cdot2310$. So $x=-3$, $y=7$. Check: $-6930+7007=77$ ✓.
2 $-83=9\cdot(-10)+7$ with $0\le7\lt9$: quotient $-10$, remainder $7$ (not $-9$ and $-2$).
3 $3(2n+1)-2(3n+1)=1$, so any common divisor divides $1$ (Theorem 5.19(1)).
4 $n^2+1=(n+1)(n-1)+2$, so $\gcd(n^2+1,n+1)=\gcd(n+1,2)$ (Theorem 5.20(a)). It is $2$ exactly when $n+1$ is even, i.e. $n$ odd; then $n^2+1$ is also even.
5 $a=12a'$, $b=12b'$ with $\gcd(a',b')=1$ and $12a'b'=360$, so $a'b'=30=2\cdot3\cdot5$. Coprime splittings with $a'\le b'$: $(1,30),(2,15),(3,10),(5,6)$. Pairs: $(12,360),(24,180),(36,120),(60,72)$.
6 If a prime $p$ divides $ab$ and $a+b$, then $p\mid a$ (say), and then $p\mid b=(a+b)-a$, contradicting $\gcd(a,b)=1$. So $\gcd(a+b,ab)=1$. If $d\mid a+b$ and $d\mid a-b$ then $d\mid2a$ and $d\mid2b$, so $d\mid\gcd(2a,2b)=2$.
7 If $m=nq+r$ then $2^m-1=2^r(2^{nq}-1)+(2^r-1)$ and $2^n-1\mid2^{nq}-1$, so $2^m-1\equiv2^r-1\pmod{2^n-1}$; thus $\gcd(2^m-1,2^n-1)=\gcd(2^n-1,2^r-1)$. The exponents run through Euclid's algorithm for $(m,n)$, ending at $2^{\gcd(m,n)}-1$. With $\gcd(12,18)=6$: $2^6-1=63$.
8 $89=55+34$, $55=34+21$, $34=21+13$, $21=13+8$, $13=8+5$, $8=5+3$, $5=3+2$, $3=2+1$, $2=2\cdot1$: nine divisions, all but the last with quotient $1$. In general $\gcd(F_{n+1},F_n)=\gcd(F_n,F_{n+1}-F_n)=\gcd(F_n,F_{n-1})=\cdots=\gcd(F_2,F_1)=1$.
II
Primes and unique factorisation.
  • 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 $v_7(1000!)=142+20+2=164$. Zeros of $125!$: $v_5=25+5+1=31$. Zeros of $2026!$: $405+81+16+3=505$.
2 $6^k=2^k3^k$; $v_2(40!)=20+10+5+2+1=38$, $v_3(40!)=13+4+1=18$. So $k=18$.
3 If $n$ has an odd factor $m\gt1$, $n=mk$, then $x+1\mid x^m+1$ for odd $m$ (since $(-1)^m+1=0$); with $x=2^k$: $2^k+1\mid2^n+1$ and $1\lt2^k+1\lt2^n+1$. So $n$ has no odd factor $\gt1$.
4 If $p_1,\dots,p_k$ were all the primes $\equiv2\pmod3$, consider $N=3p_1\cdots p_k-1\equiv2\pmod3$. Its prime factors are not $3$; if all were $\equiv1\pmod3$, so would be $N$. So some prime factor $q\equiv2\pmod3$ divides $N$, and $q=p_i$ divides $3p_1\cdots p_k-N=1$. Contradiction.
5 Sophie Germain's identity: $n^4+4=(n^2+2)^2-(2n)^2=(n^2-2n+2)(n^2+2n+2)$. For $n\gt1$ the smaller factor $(n-1)^2+1\ge2$, so both factors exceed $1$.
6 $\binom{2n}n=\frac{(2n)!}{n!\,n!}$: $p$ divides $(2n)!$ (as $p\le2n$) but not $n!$ (as $p\gt n$, and $p$ is prime), so $p\mid\binom{2n}{n}$ by Euclid's lemma applied to $\binom{2n}{n}\cdot n!^2=(2n)!$. Also $\binom{2n}{n}\lt\sum_k\binom{2n}{k}=2^{2n}=4^n$.
7 If $\log_{10}2=u/v$ with $u,v\in\mathbb{N}$, then $2^v=10^u=2^u5^u$, and unique factorisation forces $u=0$ — but $\log_{10}2\gt0$. Contradiction.
8 True. We may take $a,b\gt0$ (if $b=0$ the claim is trivial; $a=0$ forces $b=0$). By Theorem 5.23(1), $a^3\mid b^2$ means $3\alpha_p\le2\beta_p$ for every prime $p$, so $\alpha_p\le\tfrac23\beta_p\le\beta_p$, hence $a\mid b$. (The variant with the exponents swapped is false: $a=8$, $b=4$ gives $a^2=64=b^3$, so $a^2\mid b^3$, but $8\nmid4$.)
III
Diophantine equations and congruences.
  • 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 $\gcd(56,72)=8$ and $8\mid40$. Divide: $7x+9y=5$. A particular solution: $x=2$, $y=-1$ ($14-9=5$). General: $x=2+9t$, $y=-1-7t$, $t\in\mathbb{Z}$.
2 $7\cdot8-11\cdot5=1$, so $(x_0,y_0)=(1600,-1000)$ and $x=1600+11t$, $y=-1000-7t$. $x\gt0\iff t\ge-145$; $y\gt0\iff t\le-143$. $t=-145,-144,-143$ give $(5,15),(16,8),(27,1)$. Check: $35+165$, $112+88$, $189+11$ — all $200$ ✓.
3 $\gcd(12,18)=6\nmid25$. But $\gcd(12,18,25)=\gcd(6,25)=1$: $6=12\cdot(-1)+18\cdot1$ and $6\cdot(-4)+25\cdot1=1$, so $(x,y,z)=(4,-4,1)$: $48-72+25=1$ ✓.
4 $\gcd(5,8)=1$; Theorem 5.27: largest impossible $5\cdot8-5-8=27$, and $\tfrac{4\cdot7}{2}=14$ impossible values ($1,2,3,4,6,7,9,11,12,14,17,19,22,27$).
5 $\gcd(15,35)=5\mid25$: five solutions. Reduce: $3x\equiv5\pmod7$; $3^{-1}\equiv5$ ($15\equiv1$), so $x\equiv25\equiv4\pmod7$. Modulo $35$: $x\equiv4,11,18,25,32$.
6 $17\cdot6=102\equiv1\pmod{101}$, so $17^{-1}\equiv6$. (By Euclid: $101=5\cdot17+16$, $17=16+1$, so $1=17-16=17-(101-5\cdot17)=6\cdot17-101$.)
7 Digit sum $3+1+4+1+5+9+2+6=31\equiv4\pmod9$. For $11$: alternating sum from the right $9-8+7-6+5-4+3-2+1=5\not\equiv0$, so $11\nmid123\,456\,789$.
8 By Fermat, $n^p\equiv n\pmod p$; if $p-1\mid k-1$ then also $n^k=n\cdot(n^{p-1})^{(k-1)/(p-1)}\equiv n$ (trivially if $p\mid n$). For $k=5$: $p=2,3,5$ have $p-1\mid4$, so $2,3,5\mid n^5-n$ and, being coprime, $30\mid n^5-n$. For $k=13$: $p-1\mid12$ for $p=2,3,5,7,13$, and $2\cdot3\cdot5\cdot7\cdot13=2730$.
9 $1+\cdots+(n-1)=\tfrac{n(n-1)}2$. If $n$ is odd, $\tfrac{n-1}2$ is an integer and the sum is $n\cdot\tfrac{n-1}{2}\equiv0$. If $n$ is even, the sum is $\tfrac n2(n-1)\equiv\tfrac n2\pmod n$ (as $\tfrac n2(n-1)=\tfrac n2 n-\tfrac n2$), which is not $0$. Answer: exactly the odd $n$.
IV
The CRT, Fermat and Wilson.
  • 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$.
1 $M=315$, $M_1=63\equiv3\pmod5$, $y_1=2$; $M_2=45\equiv3\pmod7$, $y_2=5$; $M_3=35\equiv8\equiv-1\pmod9$, $y_3=8$. $x\equiv1\cdot63\cdot2+2\cdot45\cdot5+3\cdot35\cdot8=126+450+840=1416\equiv1416-4\cdot315=156\pmod{315}$. Check: $156=155+1=154+2=153+3$ ✓.
2 $\gcd(10,15)=5\mid12-7$: $x=7+10t$, $10t\equiv5\pmod{15}$, $2t\equiv1\pmod3$, $t\equiv2$: $x\equiv27\pmod{30}$. For $13$: $13-7=6$ and $5\nmid6$ — no solution.
3 $x\equiv4\pmod9$, $x\equiv6\pmod{14}$, coprime moduli. $x=6+14t$, $14t\equiv-2\pmod9$, $5t\equiv7\pmod9$; $5^{-1}\equiv2$, so $t\equiv14\equiv5$: $x=76$. Answer: hours $x\equiv76\pmod{126}$, i.e. $76,202,328,\dots$; first at hour $76$. Check: $76=9\cdot8+4=14\cdot5+6$ ✓.
4 $360=8\cdot9\cdot5$. Roots: mod $8$: $1,3,5,7$ (four); mod $9$: $\pm1$ (two); mod $5$: $\pm1$ (two). By Theorem 5.32: $4\cdot2\cdot2=16$.
5 $2^{12}\equiv1\pmod{13}$ and $1000=12\cdot83+4$: $2^{1000}\equiv2^4=16\equiv3$. For $77$: mod $7$, $2^3\equiv1$ and $100\equiv1\pmod3$, so $2^{100}\equiv2$; mod $11$, $2^{10}\equiv1$, so $2^{100}\equiv1$. CRT: $x\equiv2\pmod7$, $x\equiv1\pmod{11}$ gives $x=23$. So $2^{100}\equiv23\pmod{77}$.
6 $18!=18\cdot17\cdot16!\equiv(-1)(-2)16!=2\cdot16!\equiv-1\pmod{19}$, so $16!\equiv-2^{-1}=-10\equiv9$. Similarly $30!=30\cdot29\cdot28!\equiv2\cdot28!\equiv-1\pmod{31}$, so $28!\equiv-16\equiv15$.
7 For $a$ coprime to $561$: $a^2\equiv1\pmod3$, $a^{10}\equiv1\pmod{11}$, $a^{16}\equiv1\pmod{17}$ (Fermat). Since $2$, $10$ and $16$ all divide $560$, $a^{560}\equiv1$ modulo $3$, $11$ and $17$, hence modulo $561$ (Theorem 5.19(3)). (Korselt's criterion: squarefree composite $n$ with $p-1\mid n-1$ for all $p\mid n$.)
8 Each of the $p-1$ terms is $\equiv1$ by Fermat, so the sum is $\equiv p-1\equiv-1\pmod p$.
9 Induction on $k$. $k=1$: $p\mid\binom pj$ for $0\lt j\lt p$. If true for $k$, then $(a+b)^{p^{k+1}}=\big((a+b)^{p^k}\big)^p\equiv\big(a^{p^k}+b^{p^k}+pc\big)^p\equiv\big(a^{p^k}+b^{p^k}\big)^p\equiv a^{p^{k+1}}+b^{p^{k+1}}\pmod p$.
10 Odd $p$: if $p^a\mid(x-1)(x+1)$, $p$ cannot divide both factors (they differ by $2$), so $p^a$ divides one of them: $x\equiv\pm1$, and these are distinct. For $2^a$, $a\ge3$: $x$ is odd, $x-1$ and $x+1$ are both even with $\gcd=2$, so one of them is divisible by $2^{a-1}$: $x\equiv\pm1\pmod{2^{a-1}}$, i.e. $x\equiv1,\ 2^{a-1}+1,\ -1,\ 2^{a-1}-1\pmod{2^a}$; all four work since $(2^{a-1}\pm1)^2=2^{2a-2}\pm2^a+1\equiv1$ when $2a-2\ge a$.
🎯 Exam corner CSIR Part BCSIR Part CGATE MA

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$.

Idea Theorem 5.29: solvable iff $d=\gcd(24,84)\mid36$, and then exactly $d$ solutions mod $84$.
Compute $\gcd(24,84)=12$ and $12\mid36$. Reduced: $2x\equiv3\pmod7$, $x\equiv5\pmod7$, giving $x=5,12,19,\dots,82$ — twelve values.
Answer (C).

E2. CSIR Part B GATE MA The remainder when $7^{222}$ is divided by $55$ is (A) $4$; (B) $14$; (C) $39$; (D) $49$.

Split $55=5\cdot11$. Mod $5$: $7\equiv2$, $2^4\equiv1$, $222\equiv2\pmod4$, so $7^{222}\equiv4$. Mod $11$: $7^{10}\equiv1$, $222\equiv2\pmod{10}$, so $7^{222}\equiv49\equiv5$.
Recombine $x\equiv4\pmod5$, $x\equiv5\pmod{11}$: $x=49$ ($49=45+4=44+5$). Options (A), (B), (C) are all $\equiv4\pmod5$ but leave remainders $4,3,6$ on division by $11$ — each satisfies only the first congruence.
Answer (D) $49$.

E3. CSIR Part B The remainder of $28!$ on division by $31$ is (A) $1$; (B) $15$; (C) $16$; (D) $30$.

Idea Wilson: $30!\equiv-1\pmod{31}$, and $30\cdot29\equiv(-1)(-2)=2$.
Compute $2\cdot28!\equiv-1\equiv30$, so $28!\equiv15$. Check: $2\cdot15=30\equiv-1$ ✓. The distractors: (A) is the residue of $29!$ (from $30\cdot29!\equiv-29!\equiv-1$), (D) that of $30!$, and (C) $=-15$ comes from a sign slip.
Answer (B).

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|$.

(A) True With $d=\gcd(a,b)$, $a=da'$, $b=db'$, $\gcd(a',b')=1$: $\gcd(a+b,a-b)=d\gcd(a'+b',a'-b')$ and the last gcd divides $2a'$ and $2b'$, hence divides $2$ (Exercise I.6).
(B) False $a=6$, $b=4$, $c=9$.
(C) True Exponents: $\min(2\alpha_p,2\beta_p)=2\min(\alpha_p,\beta_p)$ (Theorem 5.23).
(D) False $a=b=c=2$: $2\cdot2=4\ne8$.
Answer (A) and (C).

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$.

(A) True $\gcd(6,8)=2\mid5-3$; e.g. $x=21$ ($21=18+3=16+5$), unique mod $24$.
(B) False $\gcd(4,6)=2\nmid2-1$: the first congruence makes $x$ odd, the second even.
(C) True Pairwise: $\gcd(9,12)=3\mid3$, $\gcd(12,15)=3\mid3$, $\gcd(9,15)=3\mid6$, so the system is solvable (Theorem 5.31), uniquely mod $\operatorname{lcm}(9,12,15)=180$. Indeed $x\equiv173$: $173=171+2=168+5=165+8$ ✓.
(D) False By the CRT it has $2\cdot2=4$ solutions: $1,4,11,14$ ($4^2=16\equiv1$, $11^2=121=8\cdot15+1$).
Answer (A) and (C).

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$.

(A) True Fermat's little theorem in the form $a^p\equiv a$, valid for all $a$ (Theorem 5.33).
(B) False $n=341=11\cdot31$: $2^{10}\equiv1\pmod{341}$ so $2^{340}\equiv1$ (Example 7).
(C) True The converse of Wilson's theorem (Theorem 5.35): for composite $n$, a proper divisor $a\gt1$ would divide $1$.
(D) True $2730=2\cdot3\cdot5\cdot7\cdot13$ and $p-1\mid12$ for each of these primes, so $n^{13}\equiv n$ modulo each (Exercise III.8).
Answer (A), (C) and (D).
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. 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.
  2. 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.
  3. 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–Teaching NexusResearch-tutored · optional, about 60 minutes

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.

  1. 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.
  2. 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$?
  3. 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.
  4. 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.

Instructor note: there are $78$ base-$2$ pseudoprimes below $10^5$ (the first are 341, 561, 645, 1105, 1387, 1729, 1905, 2047) against $9591$ odd primes, and $16$ Carmichael numbers below $10^5$: 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361. For $n=561$, $a=2$: $560=2^4\cdot35$, $2^{35}\equiv263$, and the squares are $166, 67, 1$ — the sequence reaches $1$ without passing through $-1\equiv560$, so Miller–Rabin exhibits $67$ as a square root of $1$ other than $\pm1$ and declares $561$ composite.

🧪 Self-check quiz

0/5 correct

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$?