---
title: "Arithmetic"
book: "High School Mathematics"
subject: math
language: en
chapter: 29
exercises: 10
source: https://one-course.com/books/math/2/en/chapter/29-arithmetic
---

# Chapter 29 — Arithmetic

Arithmetic studies the [integers](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets): [divisibility](#def-g12-arith-divides), [prime numbers](#def-g12-arith-prime), 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](#def-g12-arith-divides) every [integer](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) 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](https://one-course.com/books/math/2/en/chapter/20-sequences#def-g12-seq-bounded)); 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](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-abs) 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](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) $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](#thm-g12-arith-euclid) 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](#def-g12-arith-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 nnn).**

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](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets), not both zero. The *greatest common divisor* $\gcd(a, b)$ is the largest [integer](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) 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](#thm-g12-arith-euclid) therefore computes $\gcd(a,b)$: the [gcd](#def-g12-arith-gcd) is the last nonzero remainder.

**Proof.** Any common divisor of $a$ and $b$ [divides](#def-g12-arith-divides) $r = a - bq$ ([Proposition 29.2](#prop-g12-arith-divprops)), 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](#def-g12-arith-gcd). The algorithm terminates because the remainders form a strictly [decreasing](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-variations) [sequence](https://one-course.com/books/math/2/en/chapter/20-sequences#def-g12-seq-sequence) of nonnegative [integers](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets). ∎

**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](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets), 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](#def-g12-arith-gcd) if and only if $au + bv = 1$ for some [integers](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) $u, v$.

**Proof.** Run [Euclid’s algorithm](#prop-g12-arith-euclidalgo) backwards: each remainder is an [integer](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) 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](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) combination of $a$ and $b$. (In [Example 29.9](#ex-g12-arith-euclidalgo): $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](#def-g12-arith-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](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) $p \geq 2$ is *prime* if its only positive divisors are $1$ and $p$.

**Proposition 29.14.**

Every [integer](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) $n \geq 2$ has a [prime](#def-g12-arith-prime) divisor; if $n$ is not [prime](#def-g12-arith-prime), it has a [prime](#def-g12-arith-prime) divisor $\leq \sqrt n$. If a [prime](#def-g12-arith-prime) $p$ [divides](#def-g12-arith-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](#def-g12-arith-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](#def-g12-arith-prime).

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

**Theorem 29.16 (Fundamental theorem of arithmetic).**

Every [integer](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) $n \geq 2$ is a product of [primes](#def-g12-arith-prime), 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](#def-g12-arith-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](#def-g12-arith-prime), with repetitions allowed). By Euclid’s lemma, $p_1$ [divides](#def-g12-arith-divides) some $q_j$, and being [prime](#def-g12-arith-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](#def-g12-arith-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](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) $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](#def-g12-arith-congruence):

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

Since $p$ [divides](#def-g12-arith-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](#def-g12-arith-prime) 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](https://one-course.com/books/math/2/en/chapter/2-algebra-equations-and-inequalities#def-g10-algebra-expand) 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](#thm-g12-arith-euclid) of $2026$ by $17$, and of $-2026$ by $17$.

**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 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](#prop-g12-arith-euclidalgo), compute $\gcd(1071, 462)$, and find [integers](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) $u, v$ with $1071u + 462v = \gcd(1071, 462)$.

**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](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) $\equiv 3 \pmod 4$ is never a sum of two squares.

**Solution of Exercise 29.4.**

Every [integer](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) 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 of Exercise 29.5.**

[Divisibility](#def-g12-arith-divides) by $2$: among $n$ and $n + 1$, one is even. [Divisibility](#def-g12-arith-divides) 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](#def-g12-arith-divides) the product. Since $\gcd(2,3) = 1$, [Corollary 29.12](#cor-g12-arith-coprimeprod) 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](https://one-course.com/books/math/2/en/chapter/20-sequences#exo-g12-seq-1), is an [integer](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets).)

**Exercise 29.6 ★★.**

Solve in $\Z$ the [congruence](#def-g12-arith-congruence) $5x \equiv 3 \pmod{11}$. (Hint: find the inverse of $5$ modulo $11$.)

**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](#def-g12-arith-congruence) by $9$:

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

The solutions are the [integers](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) $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](https://one-course.com/books/math/2/en/chapter/2-algebra-equations-and-inequalities#def-g10-algebra-equation)

$$
17x - 40y = 1,
$$

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

**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](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#ex-g10-numbers-classify), using the uniqueness of [prime](#def-g12-arith-prime) factorization (compare the exponent of $2$ on both sides of $a^2 = 2b^2$).

**Solution of Exercise 29.8.**

Suppose $\sqrt2 = \frac ab$ with $a, b \in \N^*$; then $a^2 = 2b^2$. In the [prime](#def-g12-arith-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](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) with different exponents of $2$ contradict the uniqueness in [Theorem 29.16](#thm-g12-arith-fta). Hence no such fraction exists: $\sqrt2 \notin \Q$.

**Exercise 29.9 ★★★.**

Let $p$ be a [prime](#def-g12-arith-prime).

1. Show that for $1 \leq k \leq p - 1$ , $p$ [divides](#def-g12-arith-divides) $\dbinom{p}{k}$ . (Hint: use $k\binom pk = p\binom{p-1}{k-1}$ , [Exercise 27.7](https://one-course.com/books/math/2/en/chapter/27-combinatorics-and-counting#exo-g12-comb-7) , and Gauss’s lemma.)
2. Deduce, by induction on $a \geq 0$ , another proof of Fermat’s little theorem in the form $a^p \equiv a \pmod p$ .

**Solution of Exercise 29.9.**

*1.* From $k\binom pk = p \binom{p-1}{k-1}$, $p$ [divides](#def-g12-arith-divides) $k\binom pk$. For $1 \leq k \leq p-1$, $p \nmid k$ and $p$ [prime](#def-g12-arith-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](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) $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 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](https://one-course.com/books/math/2/en/chapter/17-descriptive-statistics#def-g11-stat-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](#def-g12-arith-congruence) ([Proposition 29.5](#prop-g12-arith-congops)), Bézout inverses ([Theorem 29.10](#thm-g12-arith-bezout)) and Fermat’s little theorem ([Exercise 29.9](#exo-g12-arith-9)). This problem checks the codes, breaks a toy version of the lock, and learns why the real lock holds.

**Part I — [Congruence](#def-g12-arith-congruence) fluency.**

1. Compute $2026 \bmod 7$ ; then the last digit of $7^{100}$ (find the cycle of powers of $7$ modulo $10$ ).
2. Fast exponentiation ( [Method 29.6](#met-g12-arith-powers) ): compute $5^{117} \bmod 13$ (start from $5^2 \equiv -1$ ).
3. Solve $3x \equiv 5 \pmod 7$ .
4. Run [Euclid’s algorithm](#prop-g12-arith-euclidalgo) on $(97, 35)$ , back-substitute to find [integers](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) $u, v$ with $97u + 35v = 1$ , and deduce the inverse of $35$ modulo $97$ .
5. State precisely when $a$ is invertible modulo $n$ , and which theorem delivers the inverse.

**Part II — Check digits.**

6. 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$ .
7. 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](#thm-g12-arith-gauss) )?
8. 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](https://one-course.com/books/math/2/en/chapter/28-complex-numbers#def-g12-complex-modulus) $10$ ?
9. 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}$ ?)
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$ .
11. In one sentence: what did the [prime](#def-g12-arith-prime) [modulus](https://one-course.com/books/math/2/en/chapter/28-complex-numbers#def-g12-complex-modulus) buy ISBN that EAN and Luhn, chained to $10$ , cannot have?

**Part III — Fermat’s lock.**

12. 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?
13. 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).
14. Encrypt the message $m = 4$ : compute $c = m^3 \bmod 33$ .
15. Decrypt: compute $c^d \bmod 33$ (use $c \equiv -2 \pmod{33}$ ) and recover the message.
16. 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](#thm-g12-arith-gauss) glues the two [congruences](#def-g12-arith-congruence) ). Where did $21 = ed$ ’s special form $1 + 20k$ enter?
17. 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](https://one-course.com/books/math/2/en/chapter/2-algebra-equations-and-inequalities#def-g10-algebra-expand) .)

**Part IV — Classics.**

18. The old Chinese soldier count (compare [Exercise 29.10](#exo-g12-arith-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$ .
19. 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.)
20. Finale — Hardy against the barcode: recap the chapter’s toolkit ( [congruence](#def-g12-arith-congruence) arithmetic, Bézout inverses, Fermat’s little theorem, gluing [coprime](#def-g12-arith-gcd) moduli) and where each clicked into place in this problem; then give the modern verdict on “unsullied”.

**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](#def-g12-arith-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](#def-g12-arith-prime) and [divides](#def-g12-arith-divides) neither factor, it cannot divide the product ([Theorem 29.11](#thm-g12-arith-gauss) / [Proposition 29.14](#prop-g12-arith-primedivides)): 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](https://one-course.com/books/math/2/en/chapter/28-complex-numbers#def-g12-complex-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](#def-g12-arith-prime) [modulus](https://one-course.com/books/math/2/en/chapter/28-complex-numbers#def-g12-complex-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](#def-g12-arith-prime). Moral: Fermat’s [congruence](#def-g12-arith-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](#def-g12-arith-gcd) 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](#def-g12-arith-prime) 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](#def-g12-arith-gcd), 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](#def-g12-arith-congruence) turned remainders into an arithmetic (Part I); Bézout minted the inverses that solve linear [congruences](#def-g12-arith-congruence) and RSA’s $d$ (questions 4, 13); Fermat’s little theorem opened and closed the lock (questions 15–16); gluing [coprime](#def-g12-arith-gcd) 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.