High School Mathematics · Grades 10–12

29Arithmetic

Arithmetic studies the integers: divisibility, prime numbers, remainders. Long considered the purest of pure mathematics, it now protects every online payment: the RSA cryptosystem rests on the theorems of Bézout, Gauss and Fermat proved in this chapter.

29.1 Divisibility and Euclidean division

Definition 29.1 (Divisibility)

Let $a, b \in \Z$ . We say $b$ divides $a$ , written $b \mid a$ , if there exists $k \in \Z$ with $a = kb$ . We also say $a$ is a multiple of $b$ .

Proposition 29.2

If $c \mid a$ and $c \mid b$ , then $c$ divides every integer combination $au + bv$ ( $u, v \in \Z$ ). If $a \mid b$ and $b \mid a$ with $a,b \in \N$ , then $a = b$ . If $a \mid b$ and $b \neq 0$ , then $\abs a \leq \abs b$ .

Proof. Write $a = kc$ , $b = lc$ : then $au + bv = (ku + lv)c$ . The other points follow from $\abs{a} = \abs{k}\,\abs{b}$ with $\abs k \geq 1$ when $b = ka \neq 0$ . ∎

Theorem 29.3 (Euclidean division)

Let $a \in \Z$ and $b \in \N^*$ . There exists a unique pair $(q, r) \in \Z \times \N$ such that

a = bq + r \qquad\text{and}\qquad 0 \leq r < b .

$q$ is the quotient and $r$ the remainder.

Proof. Existence. The set of multiples of $b$ not exceeding $a$ has a largest element $bq$ (it is nonempty and bounded above); set $r = a - bq$ . By maximality, $b(q+1) > a$ , so $0 \leq r < b$ . Uniqueness. If $bq + r = bq' + r'$ with $0 \leq r, r' < b$ , then $b(q - q') = r' - r$ and $\abs{r' - r} < b$ : a multiple of $b$ of absolute value less than $b$ must be $0$ , so $r = r'$ and $q = q'$ . ∎

29.2 Congruences

Definition 29.4 (Congruence)

Let $n \in \N^*$ . Two integers $a, b$ are congruent modulo $n$ , written $a \equiv b \pmod n$ , if $n \mid (a - b)$ — equivalently, if $a$ and $b$ have the same remainder in the Euclidean division by $n$ .

Proposition 29.5 (Compatibility with operations)

If $a \equiv b \pmod n$ and $c \equiv d \pmod n$ , then

a + c \equiv b + d, \qquad ac \equiv bd, \qquad a^k \equiv b^k \ (k \in \N) \pmod n .

Proof. $n$ divides $(a-b) + (c-d) = (a+c) - (b+d)$ , and $ac - bd = a(c - d) + d(a - b)$ is also a multiple of $n$ . The power rule follows by induction from the product rule. ∎

Method 29.6 (Computing powers modulo $n$ )

To compute $a^k \bmod n$ , reduce the base modulo $n$ , then look for a small power of $a$ congruent to $\pm1$ , and use it to collapse the exponent. For instance $2^{100} \bmod 7$ : since $2^3 = 8 \equiv 1 \pmod 7$ and $100 = 3\times33 + 1$ ,

2^{100} = \left(2^{3}\right)^{33} \times 2 \equiv 1^{33}\times 2 = 2 \pmod 7 .

29.3 GCD, Bézout and Gauss

Definition 29.7 (GCD)

Let $a, b$ be integers, not both zero. The greatest common divisor $\gcd(a, b)$ is the largest integer dividing both $a$ and $b$ . When $\gcd(a,b) = 1$ , $a$ and $b$ are said to be coprime.

Proposition 29.8 (Euclid’s algorithm)

If $a = bq + r$ ( $b \neq 0$ ), then $\gcd(a, b) = \gcd(b, r)$ . Iterating the Euclidean division therefore computes $\gcd(a,b)$ : the gcd is the last nonzero remainder.

Proof. Any common divisor of $a$ and $b$ divides $r = a - bq$ (Proposition 29.2), hence is a common divisor of $b$ and $r$ ; and conversely, since $a = bq + r$ . The two pairs have the same common divisors, so the same gcd. The algorithm terminates because the remainders form a strictly decreasing sequence of nonnegative integers. ∎

Example 29.9

$\gcd(252, 198)$ : $252 = 198 + 54$ ; $198 = 3\times54 + 36$ ; $54 = 36 + 18$ ; $36 = 2 \times 18 + 0$ . Hence $\gcd(252,198) = 18$ .

Theorem 29.10 (Bézout’s identity)

Let $a, b$ be integers, not both zero, and $d = \gcd(a,b)$ . There exist $u, v \in \Z$ such that

au + bv = d .

In particular, $a$ and $b$ are coprime if and only if $au + bv = 1$ for some integers $u, v$ .

Proof. Run Euclid’s algorithm backwards: each remainder is an integer combination of the previous two, and the initial data $a, b$ are combinations of themselves; by descending substitution, the last nonzero remainder $d$ is an integer combination of $a$ and $b$ . (In Example 29.9: $18 = 54 - 36 = 54 - (198 - 3\times54) = 4\times54 - 198 = 4(252 - 198) - 198 = 4\times252 - 5\times198$ .)

For the equivalence: if $\gcd(a,b) = 1$ , Bézout provides $u, v$ ; conversely, any common divisor of $a$ and $b$ divides $au + bv = 1$ , forcing $\gcd(a,b) = 1$ . ∎

Theorem 29.11 (Gauss’s lemma)

Let $a, b, c \in \Z$ . If $a \mid bc$ and $\gcd(a, b) = 1$ , then $a \mid c$ .

Proof. Bézout gives $au + bv = 1$ ; multiply by $c$ : $acu + bcv = c$ . Both terms of the left side are multiples of $a$ (the second because $a \mid bc$ ), hence so is $c$ . ∎

Corollary 29.12

If $a \mid c$ , $b \mid c$ and $\gcd(a,b) = 1$ , then $ab \mid c$ .

Proof. Write $c = ak$ . From $b \mid ak$ and $\gcd(a,b)=1$ , Gauss gives $b \mid k$ , say $k = bl$ ; then $c = abl$ . ∎

29.4 Prime numbers

Definition 29.13 (Prime)

An integer $p \geq 2$ is prime if its only positive divisors are $1$ and $p$ .

Proposition 29.14

Every integer $n \geq 2$ has a prime divisor; if $n$ is not prime, it has a prime divisor $\leq \sqrt n$ . If a prime $p$ divides a product $ab$ , then $p \mid a$ or $p \mid b$ (Euclid’s lemma).

Proof. The smallest divisor $d \geq 2$ of $n$ is prime (any proper divisor of $d$ would be a smaller divisor of $n$ ). If $n = de$ is composite with $2 \leq d \leq e$ , then $d^2 \leq de = n$ , so $d \leq \sqrt n$ . For Euclid’s lemma: if $p \nmid a$ , then $\gcd(p, a) = 1$ (the only divisors of $p$ are $1$ and $p$ ), and Gauss’s lemma gives $p \mid b$ . ∎

Theorem 29.15 (Euclid)

There are infinitely many primes.

Proof. Given any finite list $p_1, \dots, p_k$ of primes, consider $N = p_1 p_2 \cdots p_k + 1$ . Some prime $p$ divides $N$ ; but no $p_i$ divides $N$ (the remainder is $1$ ), so $p$ is a prime not in the list. No finite list exhausts the primes. ∎

Theorem 29.16 (Fundamental theorem of arithmetic)

Every integer $n \geq 2$ is a product of primes, and this factorization is unique up to the order of the factors:

n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r}, \qquad p_1 < p_2 < \dots < p_r \text{ primes},\ \alpha_i \geq 1 .

Proof. Existence, by strong induction: $n$ prime is its own factorization; otherwise $n = de$ with $2 \leq d, e < n$ , and both factor by the induction hypothesis. Uniqueness: suppose $p_1\cdots p_s = q_1 \cdots q_t$ (primes, with repetitions allowed). By Euclid’s lemma, $p_1$ divides some $q_j$ , and being prime, $p_1 = q_j$ ; cancel and repeat. The two factorizations match term by term. ∎

Theorem 29.17 (Fermat’s little theorem)

Let $p$ be prime and $a \in \Z$ with $p \nmid a$ . Then

a^{p-1} \equiv 1 \pmod p .

For every $a \in \Z$ (no coprimality assumed), $a^p \equiv a \pmod p$ .

Proof. Consider the $p - 1$ integers $a, 2a, 3a, \dots, (p-1)a$ modulo $p$ . None is $\equiv 0$ (if $p \mid ka$ with $1 \leq k \leq p-1$ , Euclid’s lemma forces $p \mid k$ , impossible), and they are pairwise distinct modulo $p$ (if $ka \equiv la$ , then $p \mid (k - l)a$ , so $p \mid k - l$ , so $k = l$ ). Hence, modulo $p$ , they are the numbers $1, 2, \dots, p-1$ in some order. Multiplying all congruences:

a^{p-1}\,(p-1)! \equiv (p-1)! \pmod p .

Since $p$ divides none of $1, \dots, p-1$ , repeated use of Euclid’s lemma allows cancelling $(p-1)!$ , leaving $a^{p-1} \equiv 1$ . The second form follows by multiplying by $a$ (and is trivial when $p \mid a$ ). ∎

Example 29.18 (Application to cryptography)

Fermat’s theorem makes exponentiation modulo $n$ reversible when the exponents are chosen suitably — the heart of the RSA cryptosystem. With $p, q$ large primes and $n = pq$ , one publishes $n$ and an exponent $e$ ; encryption is $x \mapsto x^e \bmod n$ . Decrypting requires an exponent $d$ with $ed \equiv 1 \pmod{(p-1)(q-1)}$ , which only someone knowing $p$ and $q$ can compute — and recovering $p, q$ from $n$ means factoring a number hundreds of digits long, which no known algorithm does in reasonable time.

29.5 Exercises

Exercise 29.1 ★

Compute the quotient and remainder of the Euclidean division of $2026$ by $17$ , and of $-2026$ by $17$ .

Solution

Solution of Exercise 29.1.

$17 \times 119 = 2023$ , so $2026 = 17 \times 119 + 3$ : quotient $119$ , remainder $3$ . For $-2026$ : $-2026 = 17\times(-120) + 14$ (indeed $17 \times 120 = 2040$ and $2040 - 2026 = 14$ ): quotient $-120$ , remainder $14$ (the remainder must lie in $\intco{0}{17}$ , so it is not $-3$ ).

Exercise 29.2 ★

What is the remainder of $7^{100}$ modulo $10$ ? (What is the last digit of $7^{100}$ ?)

Solution

Solution of Exercise 29.2.

Modulo $10$ : $7^2 = 49 \equiv 9 \equiv -1$ . Hence $7^{100} = \left(7^2\right)^{50} \equiv (-1)^{50} = 1 \pmod{10}$ : the last digit of $7^{100}$ is $1$ .

Exercise 29.3 ★

Using Euclid’s algorithm, compute $\gcd(1071, 462)$ , and find integers $u, v$ with $1071u + 462v = \gcd(1071, 462)$ .

Solution

Solution of Exercise 29.3.

Euclid: $1071 = 2\times462 + 147$ ; $462 = 3\times147 + 21$ ; $147 = 7\times21 + 0$ . So $\gcd = 21$ .

Back-substitution: $21 = 462 - 3\times147 = 462 - 3(1071 - 2\times462) = 7\times462 - 3\times1071$ . Thus $u = -3$ , $v = 7$ : $1071\times(-3) + 462\times7 = 21$ .

Exercise 29.4 ★

Show that for every $n \in \Z$ , $n^2$ is congruent to $0$ or $1$ modulo $4$ . Deduce that an integer $\equiv 3 \pmod 4$ is never a sum of two squares.

Solution

Solution of Exercise 29.4.

Every integer is $\equiv 0, 1, 2$ or $3 \pmod 4$ , and squaring: $0^2 \equiv 0$ , $1^2 \equiv 1$ , $2^2 = 4 \equiv 0$ , $3^2 = 9 \equiv 1$ . So $n^2 \equiv 0$ or $1 \pmod 4$ . A sum of two squares is then congruent to $0 + 0$ , $0 + 1$ or $1 + 1$ , i.e. to $0$ , $1$ or $2 \pmod 4$ — never to $3$ .

Exercise 29.5 ★★

Show that for all $n \in \N$ , $n(n+1)(2n+1)$ is divisible by $6$ .

Solution

Solution of Exercise 29.5.

Divisibility by $2$ : among $n$ and $n + 1$ , one is even. Divisibility by $3$ : if $n \equiv 0$ , then $3 \mid n$ ; if $n \equiv 1 \pmod 3$ , then $2n + 1 \equiv 3 \equiv 0$ ; if $n \equiv 2$ , then $n + 1 \equiv 0$ . In all cases $3$ divides the product. Since $\gcd(2,3) = 1$ , Corollary 29.12 gives $6 \mid n(n+1)(2n+1)$ . (This also re-proves that $\frac{n(n+1)(2n+1)}{6}$ , the sum of squares of Exercise 20.1, is an integer.)

Exercise 29.6 ★★

Solve in $\Z$ the congruence $5x \equiv 3 \pmod{11}$ . (Hint: find the inverse of $5$ modulo $11$ .)

Solution

Solution of Exercise 29.6.

We look for the inverse of $5$ modulo $11$ : testing (or Bézout), $5 \times 9 = 45 = 44 + 1 \equiv 1 \pmod{11}$ . Multiplying the congruence by $9$ :

x \equiv 9 \times 3 = 27 \equiv 5 \pmod{11}.

The solutions are the integers $x = 5 + 11k$ , $k \in \Z$ . (Check: $5\times5 = 25 \equiv 3 \pmod{11}$ .)

Exercise 29.7 ★★

Solve in $\Z \times \Z$ the Diophantine equation

17x - 40y = 1,

then describe all solutions of $17x - 40y = 6$ .

Solution

Solution of Exercise 29.7.

$\gcd(17, 40) = 1$ , so solutions exist. Euclid: $40 = 2\times17 + 6$ ; $17 = 2\times6 + 5$ ; $6 = 5 + 1$ . Back-substituting: $1 = 6 - 5 = 6 - (17 - 2\times6) = 3\times6 - 17 = 3(40 - 2\times17) - 17 = 3\times40 - 7\times17$ . Hence $17\times(-7) - 40\times(-3) = 1$ : the particular solution $(x_0, y_0) = (-7, -3)$ .

General solution of $17x - 40y = 1$ : subtracting the particular relation, $17(x + 7) = 40(y + 3)$ ; since $\gcd(17, 40) = 1$ , Gauss gives $40 \mid x + 7$ , so $x = -7 + 40k$ and then $y = -3 + 17k$ , $k \in \Z$ (all of which check).

For $17x - 40y = 6$ , multiply the particular solution by $6$ : $(x_1, y_1) = (-42, -18)$ , and the same reasoning gives

x = -42 + 40k, \qquad y = -18 + 17k, \qquad k \in \Z .

(E.g. $k = 2$ : $x = 38$ , $y = 16$ ; indeed $17\times38 - 40\times16 = 646 - 640 = 6$ .)

Exercise 29.8 ★★

Show that $\sqrt2$ is irrational, using the uniqueness of prime factorization (compare the exponent of $2$ on both sides of $a^2 = 2b^2$ ).

Solution

Solution of Exercise 29.8.

Suppose $\sqrt2 = \frac ab$ with $a, b \in \N^*$ ; then $a^2 = 2b^2$ . In the prime factorization of a square, every exponent is even; so the exponent of $2$ in $a^2$ is even, while in $2b^2$ it is odd (one more than an even number). Two factorizations of the same integer with different exponents of $2$ contradict the uniqueness in Theorem 29.16. Hence no such fraction exists: $\sqrt2 \notin \Q$ .

Exercise 29.9 ★★★

Let $p$ be a prime.

Show that for $1 \leq k \leq p - 1$ , $p$ divides $\dbinom{p}{k}$ . (Hint: use $k\binom pk = p\binom{p-1}{k-1}$ , Exercise 27.7, and Gauss’s lemma.)
Deduce, by induction on $a \geq 0$ , another proof of Fermat’s little theorem in the form $a^p \equiv a \pmod p$ .

Solution

Solution of Exercise 29.9.

1. From $k\binom pk = p \binom{p-1}{k-1}$ , $p$ divides $k\binom pk$ . For $1 \leq k \leq p-1$ , $p \nmid k$ and $p$ prime give $\gcd(p, k) = 1$ , so Gauss’s lemma yields $p \mid \binom pk$ .

2. Induction on $a$ . For $a = 0$ : $0^p \equiv 0$ . Assume $a^p \equiv a \pmod p$ . By the binomial theorem,

(a+1)^p = \sum_{k=0}^{p} \binom pk a^k \equiv a^p + 1 \pmod p,

all middle terms vanishing modulo $p$ by point 1. By the induction hypothesis, $(a+1)^p \equiv a + 1 \pmod p$ . This proves $a^p \equiv a$ for all $a \in \N$ , and the case $a < 0$ follows by writing $a \equiv a + kp$ for a suitable positive representative.

Exercise 29.10 ★★★

(Chinese remainder problem.) Find all integers $n$ such that

n \equiv 2 \pmod 3, \qquad n \equiv 3 \pmod 5, \qquad n \equiv 2 \pmod 7 .

(Hint: solve the first two conditions, then incorporate the third; Bézout coefficients help.)

Solution

Solution of Exercise 29.10.

$n \equiv 2 \pmod 3$ and $n \equiv 3 \pmod 5$ : write $n = 2 + 3s$ ; then $2 + 3s \equiv 3 \pmod 5$ , i.e. $3s \equiv 1 \pmod 5$ . The inverse of $3$ modulo $5$ is $2$ ( $3\times2 = 6 \equiv 1$ ), so $s \equiv 2 \pmod 5$ , say $s = 2 + 5t$ , and $n = 8 + 15t$ : the first two conditions mean $n \equiv 8 \pmod{15}$ .

Adding $n \equiv 2 \pmod 7$ : $8 + 15t \equiv 2 \pmod 7$ , and $15 \equiv 1 \pmod 7$ , so $t \equiv -6 \equiv 1 \pmod 7$ , say $t = 1 + 7u$ . Hence $n = 23 + 105u$ :

n \equiv 23 \pmod{105}.

(Check: $23 = 3\times7 + 2 = 5\times4 + 3 = 7\times3 + 2$ .)

29.6 Problem: Secret codes and check digits

Problem 29.1

Weekend problem — congruences guard every barcode and credit card, and Fermat’s little theorem runs the lock on the world’s secrets

G. H. Hardy boasted in 1940 that number theory was “unsullied” by applications. Eighty years later, every barcode beep, every credit-card payment and every encrypted message contradicts him — with exactly this chapter’s tools: congruences (Proposition 29.5), Bézout inverses (Theorem 29.10) and Fermat’s little theorem (Exercise 29.9). This problem checks the codes, breaks a toy version of the lock, and learns why the real lock holds.

Part I — Congruence fluency.

Compute $2026 \bmod 7$ ; then the last digit of $7^{100}$ (find the cycle of powers of $7$ modulo $10$ ).
Fast exponentiation (Method 29.6): compute $5^{117} \bmod 13$ (start from $5^2 \equiv -1$ ).
Solve $3x \equiv 5 \pmod 7$ .
Run Euclid’s algorithm on $(97, 35)$ , back-substitute to find integers $u, v$ with $97u + 35v = 1$ , and deduce the inverse of $35$ modulo $97$ .
State precisely when $a$ is invertible modulo $n$ , and which theorem delivers the inverse.

Part II — Check digits.

ISBN-10: the ten digits $d_1 \dots d_{10}$ of a book code must satisfy $10d_1 + 9d_2 + \dots + 2d_9 + 1d_{10} \equiv 0 \pmod{11}$ . Verify the real ISBN $0\,306\,40615\,2$ .
Prove that the ISBN scheme detects every single-digit error: if one digit changes by $d \not\equiv 0$ , the weighted sum changes by $w d$ with $1 \leq w \leq 10$ — why can this never be $\equiv 0 \pmod{11}$ (Theorem 29.11)?
Prove it also detects every transposition of two adjacent (distinct) digits. Then explain the design secret: what property of $11$ made both proofs work, and what could go wrong with modulus $10$ ?
EAN-13 barcodes weight the digits $1, 3, 1, 3, \dots$ modulo $10$ . Compute the check digit completing $978\,2940199\,05$ . Which adjacent transpositions does EAN fail to detect? (When is $2(a - b) \equiv 0 \pmod{10}$ ?)
Credit cards use Luhn’s scheme: from the right, double every second digit (subtracting $9$ when the double exceeds $9$ ), sum everything, and require a multiple of $10$ . Verify the test number $4539\,1488\,0343\,6467$ .
In one sentence: what did the prime modulus buy ISBN that EAN and Luhn, chained to $10$ , cannot have?

Part III — Fermat’s lock.

A trap before the treasure: compute $2^{10} \bmod 341$ , deduce $2^{340} \bmod 341$ — and then factor $341$ . What does this example (a Fermat pseudoprime) say about using Fermat’s little theorem as a primality test?
RSA in miniature: take $p = 3$ , $q = 11$ , so $n = 33$ and $(p-1)(q-1) = 20$ ; the public exponent is $e = 3$ . Find the private exponent $d$ with $3d \equiv 1 \pmod{20}$ (question 4’s method).
Encrypt the message $m = 4$ : compute $c = m^3 \bmod 33$ .
Decrypt: compute $c^d \bmod 33$ (use $c \equiv -2 \pmod{33}$ ) and recover the message.
Why decryption always works: show that $m^{21} \equiv m$ both modulo $3$ and modulo $11$ (Fermat’s little theorem in each world), and conclude modulo $33$ (Theorem 29.11 glues the two congruences). Where did $21 = ed$ ’s special form $1 + 20k$ enter?
The lock’s safety: everyone knows $n$ and $e$ ; recovering $d$ requires $(p-1)(q-1)$ , hence the factors of $n$ . Our $33$ factors at sight — why does the same scheme, with $n$ of six hundred digits, protect the world’s banks? (One sentence on the asymmetry between multiplying and factoring.)

Part IV — Classics.

The old Chinese soldier count (compare Exercise 29.10): a number of soldiers leaves remainder $2$ when ranked by $3$ and remainder $3$ when ranked by $5$ . Find all possible counts, and explain why the answer is unique modulo $15$ .
One-line proofs at last: from $10 \equiv 1 \pmod 9$ , prove that every number is congruent to its digit sum modulo $9$ ; from $10 \equiv -1 \pmod{11}$ , derive the alternating-sum rule for $11$ . (The Middle School volume proved these with explicit algebra — admire the compression.)
Finale — Hardy against the barcode: recap the chapter’s toolkit (congruence arithmetic, Bézout inverses, Fermat’s little theorem, gluing coprime moduli) and where each clicked into place in this problem; then give the modern verdict on “unsullied”.

Solution

Solution of Problem 29.1.

1. $2026 = 289 \times 7 + 3$ : $2026 \equiv 3 \pmod 7$ . Powers of $7$ mod $10$ : $7, 9, 3, 1$ , cycle of length $4$ ; $100 \equiv 0 \pmod 4$ : last digit of $7^{100}$ is $1$ .

2. $5^2 = 25 \equiv -1 \pmod{13}$ , so $5^{116} = \left(5^2\right)^{58} \equiv (-1)^{58} = 1$ and $5^{117} \equiv 5 \pmod{13}$ .

3. The inverse of $3$ modulo $7$ is $5$ ( $15 \equiv 1$ ): $x \equiv 5 \times 5 = 25 \equiv 4 \pmod 7$ .

4. $97 = 2 \times 35 + 27$ ; $35 = 27 + 8$ ; $27 = 3 \times 8 + 3$ ; $8 = 2 \times 3 + 2$ ; $3 = 2 + 1$ . Back-substituting: $1 = 97 \times 13 + 35 \times (-36)$ . So $35 \times (-36) \equiv 1 \pmod{97}$ : the inverse of $35$ is $-36 \equiv 61 \pmod{97}$ .

5. $a$ is invertible modulo $n$ exactly when $\gcd(a, n) = 1$ : Bézout provides $au + nv = 1$ , i.e. $au \equiv 1$ ; conversely an inverse forces the gcd to divide $1$ .

6. $0{\cdot}10 + 3{\cdot}9 + 0{\cdot}8 + 6{\cdot}7 + 4{\cdot}6 + 0{\cdot}5 + 6{\cdot}4 + 1{\cdot}3 + 5{\cdot}2 + 2{\cdot}1 = 132 = 12 \times 11 \equiv 0 \pmod{11}$ : valid.

7. The sum changes by $wd$ with $1 \leq w \leq 10$ and $1 \leq \abs d \leq 9$ : since $11$ is prime and divides neither factor, it cannot divide the product (Theorem 29.11 / Proposition 29.14): the changed sum is never again $\equiv 0$ : every single-digit error trips the alarm.

8. Swapping adjacent digits $a, b$ (weights $w + 1, w$ ) changes the sum by $(w+1)b + wa - (w+1)a - wb = b - a \not\equiv 0$ for $a \neq b$ : detected. The secret is the primality of $11$ : modulo $10$ , products like $5 \times 2$ vanish with neither factor zero, so a weight- $5$ error of $\pm 2$ (or an unlucky transposition) could slip through.

9. Weighted sum of the twelve digits: $119$ ; the check digit must complete it to a multiple of $10$ : $1$ (full code $978\,2940199\,051$ ). EAN misses adjacent transpositions with $2(a - b) \equiv 0 \pmod{10}$ , i.e. $\abs{a - b} = 5$ : swapping a $2$ and a $7$ , say, passes unseen — the price of the friendly modulus $10$ .

10. Doubling every second digit from the right and folding ( $16 \to 7$ , etc.), the sum comes to $80 \equiv 0 \pmod{10}$ : the test card validates.

11. With a prime modulus every weight is invertible, so all single errors and all adjacent transpositions are caught — ISBN’s luxury; mod- $10$ schemes keep human-friendly digits and accept a short blind spot.

12. $2^{10} = 1024 = 3 \times 341 + 1 \equiv 1 \pmod{341}$ , hence $2^{340} = \left(2^{10}\right)^{34} \equiv 1$ . Yet $341 = 11 \times 31$ is composite: it passes Fermat’s test at base $2$ while being no prime. Moral: Fermat’s congruence is necessary, not sufficient — primality testing needs sharper tools (and gets them, in the university volumes).

13. $3d \equiv 1 \pmod{20}$ : $d = 7$ ( $21 = 20 + 1$ ).

14. $c = 4^3 = 64 \equiv 31 \pmod{33}$ .

15. $31 \equiv -2$ : $(-2)^7 = -128$ , and $-128 + 4 \times 33 = 4$ : the ciphertext decrypts to $m = 4$ . The lock turns.

16. Modulo $3$ : if $3 \nmid m$ , $m^2 \equiv 1$ (Fermat), so $m^{21} = m \cdot \left(m^2\right)^{10} \equiv m$ ; if $3 \mid m$ , both sides are $\equiv 0$ . Modulo $11$ : $m^{10} \equiv 1$ or $11 \mid m$ , and $m^{21} = m \cdot \left(m^{10}\right)^2 \equiv m$ . Both $3$ and $11$ divide $m^{21} - m$ , and being coprime their product $33$ does too (Gauss): $m^{21} \equiv m \pmod{33}$ . The exponent $ed = 21 = 1 + 20k$ was built so that both Fermat exponents ( $2$ and $10$ , dividing $20$ ) disappear.

17. Multiplying two $300$ -digit primes takes a microsecond; recovering them from their product defeats every known algorithm and all the world’s computers — the lock is a one-way street. (Our $n = 33$ is the street at toy scale, walkable in both directions.)

18. Testing residues (or building with Bézout): $n \equiv 8 \pmod{15}$ : the counts $8, 23, 38, 53, \dots$ Uniqueness modulo $15$ : two solutions differ by a multiple of $3$ and of $5$ , hence of $15$ ( $3$ and $5$ coprime, Gauss). The general with $1000$ soldiers announces “ $8$ ” by three quick line-ups — the ancient headcount trick.

19. $10 \equiv 1 \pmod 9$ gives $10^k \equiv 1$ , so $\sum d_k 10^k \equiv \sum d_k$ : a number and its digit sum are congruent modulo $9$ (and modulo $3$ ). And $10 \equiv -1 \pmod{11}$ gives $\sum d_k 10^k \equiv \sum (-1)^k d_k$ : the alternating rule. Two childhood rules, one line each.

20. Congruences turned remainders into an arithmetic (Part I); Bézout minted the inverses that solve linear congruences and RSA’s $d$ (questions 4, 13); Fermat’s little theorem opened and closed the lock (questions 15–16); gluing coprime moduli counted soldiers and finished the proof (questions 16, 18). Verdict on Hardy: the purest theorem he knew now guards every purchase — purity, given time, is the most applicable thing there is.