0.5 Integers mod n, gcd and Bézout

Dividing with remainder gives a way to find the greatest common divisor (Euclid's algorithm) and to write it as a combination of the two numbers (Bézout). That in turn decides when you can divide in clock arithmetic, proves unique factorization into primes, and powers RSA encryption and check digits.

Which day of the week is it $100$ days from today? You divide $100$ by $7$ and keep the remainder. That is arithmetic where only remainders matter, and this chapter makes it rigorous. Two questions drive everything. When can you divide in such arithmetic, so that a rule like " $3x \equiv 4$ " has an answer? And what does the greatest common divisor, which you used in school to simplify fractions, really tell you? The answer to both is one identity of Bézout. From it come the factorization of every integer into primes, Fermat’s little theorem, the correctness of RSA encryption, and the check digits on books and bank cards.

Before you start

0.2: the well-ordering principle, induction and strong induction, and proof by contradiction. 0.4: equivalence relations and classes. Three quick checks.

Quick checkWhich of these sets is guaranteed by the well-ordering principle to have a smallest element?

Quick checkFor the relation

a \sim b

iff

5 \mid (a - b)

, which of

3

13

-2

are in the class

[8]

Quick checkWhat is the remainder when

-7

is divided by

3

The picture

Take a week of seven days, numbered $0$ (Sunday) to $6$ (Saturday). Counting $100$ days forward from a Wednesday ( $3$ ) moves you $100 \bmod 7 = 2$ places ahead, since $100 = 14 \cdot 7 + 2$ . Friday. Only the remainder matters, because every full week returns you to the same day.

Now multiply. Here are the multiplication tables of the nonzero remainders, mod $7$ and mod $6$ .

$\times$ mod 7	1	2	3	4	5	6
1	1	2	3	4	5	6
2	2	4	6	1	3	5
3	3	6	2	5	1	4
4	4	1	5	2	6	3
5	5	3	1	6	4	2
6	6	5	4	3	2	1

$\times$ mod 6	1	2	3	4	5
1	1	2	3	4	5
2	2	4	0	2	4
3	3	0	3	0	3
4	4	2	0	4	2
5	5	4	3	2	1

Look at the row of $3$ in the first table: it contains $1$ exactly once ( $3 \cdot 5 \equiv 1$ ), so $3$ has an “inverse” $5$ that undoes multiplication by $3$ . Every row of the mod 7 table is a shuffle of $1, \dots, 6$ . In the mod 6 table the rows of $2$ , $3$ and $4$ have repeats and no $1$ : those numbers have no inverse, and $2 \cdot 3 \equiv 0$ even though neither factor is $0$ . The difference between $7$ and $6$ is that $7$ is prime. The exact rule, for any modulus, is the main theorem of this chapter: $a$ has an inverse mod $n$ iff $\gcd(a, n) = 1$ .

The idea, in words

Why· The chain of ideas

Everything follows from one picture. Dividing $a$ by $b$ with a remainder splits $a$ into a multiple of $b$ plus a leftover smaller than $b$ . If a number $d$ divides both $a$ and $b$ , it also divides the leftover, so the common divisors of $(a, b)$ are the common divisors of $(b, \text{leftover})$ , and the problem has become smaller. Repeating gives Euclid’s algorithm. Running the algorithm backwards writes the gcd as $ax + by$ , which is Bézout’s identity. That identity is a way to divide: if $\gcd(a, n) = 1$ then $ax + ny = 1$ , so $ax \equiv 1 \pmod n$ and $x$ is an inverse of $a$ . Primes are the numbers with no common factor with anything smaller, so division always works mod a prime, and primes cannot be split, which gives unique factorization.

Where this came from· Euclid, Bachet and Bézout

Euclid’s Elements (around 300 BC) contains, in Book VII, the repeated-division method for finding the greatest common divisor of two numbers, and Proposition 30 of that book says that a prime dividing a product divides one of the factors, which is the key lemma below. The identity that the gcd is a combination $ax + by$ was proved for integers by Claude Gaspar Bachet de Méziriac in the second edition of his collection of number puzzles (1624). Étienne Bézout, later in the eighteenth century, proved the corresponding statement for polynomials, and the integer statement came to carry his name. The problem all of them worked on is still the right one to keep in mind: given two sizes, which amounts can be measured out using only multiples of each?

Definitions and theorems

Division with remainder

Theorem B Hammack 5.2

Division algorithm

Let $a$ be an integer and $b$ a positive integer. Then there exist unique integers $q$ (the quotient) and $r$ (the remainder) such that

a = bq + r, \qquad 0 \le r < b.

We write $r = a \bmod b$ .

In one lineFor any integer $a$ and positive integer $b$ there are unique integers $q$ and $r$ with $a = bq + r$ and $0 \le r < b$ .

Why it is trueSubtract multiples of $b$ from $a$ as long as the result stays non-negative; the smallest non-negative result is the remainder.

Proofstandard

The idea: Existence: among all the non-negative numbers of the form a minus a multiple of b, take the smallest, using well-ordering. It must be smaller than b, or we could subtract b once more. Uniqueness: two remainders differ by a multiple of b, but they are both less than b apart.

Let

S = \{a - bk : k \in \mathbb Z,\ a - bk \ge 0\}

We consider every leftover

a - bk

we can get by subtracting multiples of

b

and that is not negative.

S

is non-empty.

Take

k = -\lvert a \rvert

: then

a - bk = a + b\lvert a \rvert \ge a + \lvert a \rvert \ge 0

, since

b \ge 1

S

has a least element; call it

r = a - bq

0 \in S

then

0

is the smallest possible element. Otherwise every element of

S

is a positive integer, and the well-ordering principle (0.2) applies.

Then

r \ge 0

and

a = bq + r

By the definition of

S

r \ge 0

Suppose

r \ge b

Proof by contradiction. If

r \ge b

then

r - b = a - b(q + 1) \ge 0

, so

r - b \in S

, and it is smaller than

r

. That contradicts

r

being the least element.

Hence

r < b

. This proves existence.

The assumption led to a contradiction.

b

divides

r' - r

Uniqueness: assume

a = bq + r = bq' + r'

with

0 \le r \le r' < b

(swap the names if needed). Subtract:

b(q - q') = r' - r

r' = r

, and then

b(q - q') = 0

gives

q = q'

But

0 \le r' - r < b

, and the only multiple of

b

in that range is

0

Worked example

Find the quotient and remainder when (a)

100

is divided by

7

and (b)

-17

is divided by

5

Solution.

(a) Find the largest multiple not above 100. $7 \cdot 14 = 98 \le 100 < 105 = 7 \cdot 15$ . So $q = 14$ . The quotient is the number of full sevens that fit.
(a) The leftover. $r = 100 - 98 = 2$ . The remainder is $a - bq$ , and it lies between $0$ and $6$ .
(b) Negative number: go below, not above. $5 \cdot (-4) = -20 \le -17 < -15 = 5 \cdot (-3)$ . So $q = -4$ . The remainder must be non-negative, so the multiple of $5$ must not exceed $-17$ . Choosing $q = -3$ would give $r = -17 + 15 = -2$ , which is negative.
(b) The leftover. $r = -17 - (-20) = 3$ . $-17 = 5 \cdot (-4) + 3$ .

Answer. (a) $100 = 7 \cdot 14 + 2$ . (b) $-17 = 5 \cdot (-4) + 3$ , so $-17 \bmod 5 = 3$ .

Divisibility

Definition B

Divides

For integers $a$ and $b$ , $a$ divides $b$ , written $a \mid b$ , if there is an integer $k$ with $b = ak$ . We also say $a$ is a divisor or factor of $b$ and $b$ is a multiple of $a$ . When $a$ does not divide $b$ , we write $a \nmid b$ . Note $a \mid 0$ for every $a$ (take $k = 0$ ), and $0 \mid b$ only if $b = 0$ .

In one line $a \mid b$ means $b$ is a whole-number multiple of $a$ : $b = ak$ for some integer $k$ .

Why it existsIt is the precise form of 'goes into evenly', and every statement about factors and remainders is built from it.

Proposition B

Divisibility facts

For integers $a, b, c$ :

If $a \mid b$ and $a \mid c$ , then $a \mid (bx + cy)$ for all integers $x, y$ .
If $a \mid b$ and $b \mid c$ , then $a \mid c$ .
If $a \mid b$ and $b \ne 0$ , then $\lvert a \rvert \le \lvert b \rvert$ .

In one lineDivisors pass through sums and multiples: if $a$ divides $b$ and $c$ , it divides $bx + cy$ for all integers $x, y$ ; divisibility chains; and a divisor of a non-zero number is at most as large in size.

Why it is trueEach is a one-line calculation from the definition $b = ak$ .

Proofstandard

The idea: Write each hypothesis as an equation b = ak and substitute.

(1) Write

b = ak

and

c = al

Definition of divides, used for both hypotheses.

Then

bx + cy = a(kx + ly)

, which is a multiple of

a

Substitute and factor out

a

. The bracket is an integer because sums and products of integers are integers.

Then

c = (ak)l = a(kl)

, a multiple of

a

(2) Write

b = ak

and

c = bl

. Substitute.

Then

\lvert b \rvert = \lvert a \rvert \lvert k \rvert \ge \lvert a \rvert

(3) Write

b = ak

. Since

b \ne 0

k \ne 0

, and a non-zero integer has size at least

1

The greatest common divisor

Definition B

Gcd

For integers $a, b$ not both zero, $\gcd(a, b)$ is the largest positive integer that divides both $a$ and $b$ . It exists: $1$ is a common divisor, and by fact 3 every common divisor is at most $\max(\lvert a \rvert, \lvert b \rvert)$ in size, so there are only finitely many. We say $a$ and $b$ are coprime (or relatively prime) if $\gcd(a, b) = 1$ . For example $\gcd(12, 18) = 6$ , $\gcd(9, 16) = 1$ , and $\gcd(a, 0) = \lvert a \rvert$ .

In one lineThe greatest common divisor of $a$ and $b$ is the largest positive integer that divides both.

Why it existsIt is the 'common measure' of two quantities, and the key to simplifying fractions and to dividing in modular arithmetic.

How do you compute a gcd when the numbers have hundreds of digits? Listing divisors is hopeless. Euclid’s insight is that one step of division makes the problem smaller without changing the answer.

Lemma B

Euclid's reduction step

If $a, b, q, r$ are integers with $a = bq + r$ and $b \ne 0$ , then $\gcd(a, b) = \gcd(b, r)$ (where $\gcd(b, 0) = \lvert b \rvert$ ).

In one lineIf $a = bq + r$ then $a$ and $b$ have exactly the same common divisors as $b$ and $r$ , so $\gcd(a, b) = \gcd(b, r)$ .

Why it is trueA number dividing $a$ and $b$ divides $a - bq = r$ , and a number dividing $b$ and $r$ divides $bq + r = a$ .

ProofEuclid VII.2

The idea: Show the two pairs have the same set of common divisors. Then they have the same largest element.

Let

d

divide both

a

and

b

. Then

d \mid a - bq = r

, so

d

is a common divisor of

b

and

r

Fact 1 with

x = 1

and

y = -q

: a divisor of

a

and

b

divides

a - qb

Conversely let

d

divide both

b

and

r

. Then

d \mid bq + r = a

, so

d

is a common divisor of

a

and

b

Fact 1 again: a divisor of

b

and

r

divides

qb + r

The pairs

(a, b)

and

(b, r)

have the same common divisors, so the same greatest common divisor.

Two sets that are equal have the same largest element.

Theorem B

Euclid's algorithm

For positive integers $a, b$ , define $r_0 = a$ , $r_1 = b$ , and, as long as $r_i \ne 0$ , divide: $r_{i-1} = q_i r_i + r_{i+1}$ with $0 \le r_{i+1} < r_i$ . Then the sequence reaches $0$ , and the last non-zero term $r_n$ equals $\gcd(a, b)$ .

In one lineRepeat 'divide the larger by the smaller and keep the remainder' until the remainder is zero; the last non-zero remainder is the gcd.

Why it is trueEach division replaces the pair by a pair with the same gcd, and the numbers strictly shrink so the process must stop.

ProofEuclid VII.2

The idea: Termination: the remainders strictly decrease and cannot go below 0. Correctness: apply the reduction step at every line.

The sequence

r_1 > r_2 > \dots \ge 0

must reach

0

after finitely many steps; say

r_{n+1} = 0

By the division algorithm each remainder satisfies

0 \le r_{i+1} < r_i

, so

r_1 > r_2 > r_3 > \dots

. A strictly decreasing sequence of non-negative integers has only finitely many terms (by well-ordering: its set of values has a least element).

\gcd(a, b) = \gcd(r_1, r_2) = \gcd(r_2, r_3) = \dots = \gcd(r_n, r_{n+1})

Euclid's reduction step applied to each line

r_{i-1} = q_i r_i + r_{i+1}

\gcd(a, b) = r_n

, the last non-zero remainder.

r_{n+1} = 0

, and

\gcd(r_n, 0) = r_n

Worked example

Compute

\gcd(252, 105)

with Euclid's algorithm.

Solution.

Divide the larger by the smaller. $252 = 2 \cdot 105 + 42$ . $2 \cdot 105 = 210 \le 252 < 315$ , leaving $252 - 210 = 42$ .
Replace the pair. Now work with $(105, 42)$ : $105 = 2 \cdot 42 + 21$ . The reduction step: $\gcd(252, 105) = \gcd(105, 42)$ .
Again. $42 = 2 \cdot 21 + 0$ . Remainder zero, so we stop. $\gcd(105, 42) = \gcd(42, 21) = 21$ .

Answer. $\gcd(252, 105) = 21$ . Check: $252 = 12 \cdot 21$ and $105 = 5 \cdot 21$ , and $12$ and $5$ have no common factor.

Your answerUse Euclid's algorithm to find

\gcd(1547, 560)

Bézout’s identity

Euclid’s algorithm finds the gcd. Running it backwards finds something more useful.

Theorem B Bachet 1624; Hammack 5.3

Bézout's identity

If $a, b$ are integers, not both zero, there exist integers $x, y$ with $ax + by = \gcd(a, b)$ . Moreover $\gcd(a, b)$ is the smallest positive integer that can be written as $ax + by$ .

In one lineThe gcd of $a$ and $b$ is always an integer combination of them: $\gcd(a, b) = ax + by$ for some integers $x, y$ . In fact it is the smallest positive number of that form.

Why it is trueLook at all positive numbers of the form $ax + by$ . The smallest one must divide $a$ and $b$ , else dividing would produce a smaller one.

ProofHammack 5.3

The idea: Let d be the smallest positive combination ax + by (it exists by well-ordering). Show d divides both a and b by dividing a by d and seeing the remainder is a smaller combination, hence zero. Then d is a common divisor, and every common divisor divides d, so d is the greatest.

Let

S = \{ax + by : x, y \in \mathbb Z,\ ax + by > 0\}

We study all the positive integers that can be built from

a

and

b

with integer coefficients.

S

is non-empty, so it has a least element

d = ax_0 + by_0

Not both of

a, b

are zero, so

a \cdot a + b \cdot b > 0

lies in

S

. Well-ordering (0.2) gives a least element.

Divide

a

d

a = qd + r

with

0 \le r < d

The division algorithm (above) applied to

a

and the positive number

d

r = a - qd = a(1 - qx_0) + b(-qy_0)

Substitute

d = ax_0 + by_0

: the remainder is again a combination of

a

and

b

.This is the key idea. A remainder from dividing by a combination is itself a combination.

r = 0

, that is

d \mid a

. The same argument gives

d \mid b

r > 0

it would be a positive combination smaller than

d

, contradicting that

d

is the least element of

S

Therefore

d = \gcd(a, b)

Now

d

is a common divisor, so

d \le \gcd(a, b)

. Conversely

\gcd(a, b)

divides

a

and

b

, so by fact 1 it divides

ax_0 + by_0 = d

, and by fact 3 it is at most

d

Proof workshopRebuild the proof of Bézout's identity

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

Quick checkWhich of these integers can be written as

12x + 18y

with integer

x, y

Corollary B

Linear combinations of two integers

Let $g = \gcd(a, b)$ . The equation $ax + by = c$ has an integer solution if and only if $g \mid c$ .

In one line $ax + by = c$ has an integer solution $(x, y)$ exactly when $\gcd(a, b)$ divides $c$ . In particular $a$ and $b$ are coprime iff $ax + by = 1$ is solvable.

Why it is trueEvery combination is a multiple of the gcd, and Bézout gives all multiples.

Proofstandard

The idea: One direction: g divides both terms. The other: scale the Bézout combination.

ax + by = c

, then

g \mid c

Fact 1:

g

divides

a

and

b

, hence divides

ax + by

Conversely, write

c = gk

and take

ax_0 + by_0 = g

g \mid c

then

c = gk

. Bézout gives

ax_0 + by_0 = g

Then

a(kx_0) + b(ky_0) = gk = c

, so

(kx_0, ky_0)

is a solution.

Multiply the Bézout identity by

k

How do you find $x$ and $y$ ? Run Euclid’s algorithm, then substitute backwards. This is the extended Euclidean algorithm.

Python labThe extended Euclidean algorithm, run by a computer

def ext_gcd(a, b):
    """Return (g, x, y) with g = gcd(a, b) = a*x + b*y."""
    if b == 0:
        return a, 1, 0
    q, r = divmod(a, b)            # a = q*b + r
    g, x, y = ext_gcd(b, r)        # g = b*x + r*y
    return g, y, x - q*y           # substitute r = a - q*b

g, x, y = ext_gcd(240, 46)
print(f"gcd = {g} = 240*({x}) + 46*({y})")
print("check:", 240*x + 46*y)

def inverse(a, n):
    g, x, _ = ext_gcd(a, n)
    if g != 1:
        return None                # no inverse unless gcd(a, n) = 1
    return x % n

print("inverse of 11 mod 26:", inverse(11, 26))

Try this. Check the trace above with ext_gcd(240, 46). Then find the inverse of $11$ mod $26$ (the answer should be $19$ ), and try two large numbers such as ext_gcd(261 - 1, 1018). The number of steps grows only like the number of digits, which is why RSA can use this on numbers with hundreds of digits.

Worked example

Solve

240x + 46y = 14

in integers, and decide whether

240x + 46y = 15

is solvable.

Solution.

Compute the gcd. From the trace above, $\gcd(240, 46) = 2$ . By the corollary, solvability depends only on whether the gcd divides the right side.
Test $14$ . $2 \mid 14$ , so a solution exists. The corollary, “if” direction.
Scale the Bézout identity. From $240(-9) + 46(47) = 2$ , multiply by $7$ : $240(-63) + 46(329) = 14$ . $14 = 7 \cdot 2$ . Check: $-15120 + 15134 = 14$ .
More solutions. Replacing $(x, y)$ by $(x + 23t,\ y - 120t)$ keeps the value, since $240 \cdot 23 = 5520 = 46 \cdot 120$ . Adding $23$ copies of $240$ and subtracting $120$ copies of $46$ changes the total by $5520 - 5520 = 0$ .
Test $15$ . $2 \nmid 15$ , so there is no solution. Every value $240x + 46y$ is even.

Answer. $(x, y) = (-63, 329)$ solves the first equation, and the second has no integer solution.

Primes and unique factorization

Definition B

Prime

An integer $p > 1$ is prime if its only positive divisors are $1$ and $p$ . An integer $n > 1$ that is not prime is composite: $n = ab$ with $1 < a, b < n$ . The number $1$ is neither. The first primes are $2, 3, 5, 7, 11, 13, \dots$

In one lineA prime is an integer greater than 1 whose only positive divisors are 1 and itself.

Why it existsPrimes are the atoms of the integers: every integer above 1 is built by multiplying primes.

The next result feels familiar, and you used it in JEE without a thought: if a prime divides a product, it divides one of the factors. It needs a proof, because it fails for composites ( $6 \mid 2 \cdot 3$ but $6$ divides neither $2$ nor $3$ ). It needs Bézout.

Lemma B Euclid VII.30

Euclid's lemma

Let $p$ be prime and $a, b$ integers. If $p \mid ab$ , then $p \mid a$ or $p \mid b$ . More generally, if $p \mid a_1 a_2 \cdots a_k$ then $p \mid a_i$ for some $i$ .

In one lineIf a prime $p$ divides a product $ab$ , then $p$ divides $a$ or $p$ divides $b$ .

Why it is trueIf $p$ does not divide $a$ , then $p$ and $a$ are coprime, so Bézout gives $1 = px + ay$ , and multiplying by $b$ shows $p \mid b$ .

ProofHammack 5.4

The idea: Assume p does not divide a, and show p must divide b. The gcd of p and a is 1 because p has only two divisors. Then Bézout gives a combination equal to 1, which turns the hypothesis into the conclusion.

Suppose

p \nmid a

. We show

p \mid b

Proof by cases (0.2): either

p \mid a

, and we are done, or

p \nmid a

. We study the second case.

\gcd(p, a) = 1

\gcd(p, a)

is a positive divisor of

p

, so it is

1

p

. It is not

p

, since

p \nmid a

Choose integers

x, y

with

px + ay = 1

Bézout's identity.

Then

pbx + aby = b

Multiply both sides by

b

Both terms on the left are multiples of

p

p

divides

pbx

because

pbx = p(bx)

, and

p

divides

ab

by hypothesis, so

p

divides

aby

p \mid b

Fact 1: a divisor of two numbers divides their sum.

The version for

k

factors follows by induction on

k

For

k

factors, induct on

k

: apply the two-factor case to

a_1

and the product

a_2 \cdots a_k

Proof workshopRebuild the proof of Euclid's lemma

Tap the lines in the order a proof would write them. Each line can only use what is already above it.

Worked example Hammack 5.4

Prove: if

a \mid bc

and

\gcd(a, b) = 1

, then

a \mid c

Solution. The plan: this is Euclid’s lemma with $a$ not required to be prime. Use Bézout to get a combination equal to $1$ , then multiply by $c$ .

Use Bézout. Since $\gcd(a, b) = 1$ , there are integers $x, y$ with $ax + by = 1$ . The coprime hypothesis is only usable through Bézout.
Multiply by $c$ . $acx + bcy = c$ . We want $c$ alone on one side, because the goal is to show $a$ divides $c$ .
Check both terms. $a \mid acx$ because it has the factor $a$ . $a \mid bcy$ because $a \mid bc$ by hypothesis. The first term is a multiple of $a$ by its shape, the second by the hypothesis.
Add. So $a$ divides $acx + bcy = c$ . A divisor of two numbers divides their sum (fact 1).

Answer. $a \mid c$ . For example, $6 \mid 4 \cdot 9$ does not give $6 \mid 9$ , because $\gcd(6, 4) = 2 \ne 1$ .

Quick check

6 \mid 4 \cdot 9 = 36

, but

6 \nmid 4

and

6 \nmid 9

. Why does this not contradict Euclid's lemma?

Theorem B Euclid IX.14; Gauss 1801

Fundamental theorem of arithmetic

Every integer $n > 1$ can be written as a product of primes $n = p_1 p_2 \cdots p_r$ (a prime is a product of one prime). If $p_1 \cdots p_r = q_1 \cdots q_s$ with all $p_i, q_j$ prime, then $r = s$ and the $q_j$ are the $p_i$ in some order.

In one lineEvery integer greater than 1 is a product of primes, in exactly one way apart from the order of the factors.

Why it is trueExistence: split a composite number into smaller ones until the pieces are prime. Uniqueness: Euclid's lemma lets you match primes from two factorizations one at a time.

ProofHammack 10.3

The idea: Existence by strong induction: a composite number is a product of two smaller numbers, each of which is a product of primes by the hypothesis. Uniqueness by induction on r: the first prime p must divide some q_j by Euclid's lemma, hence equals it; cancel and repeat.

S(2)

holds, since

2

is prime. Let

n > 2

and assume

S(k)

for

2 \le k < n

Existence, by strong induction on

n

(0.2). Let

S(n)

say that

n

is a product of primes. Assume

S(k)

for all

2 \le k < n

Case 1:

n

is prime. Done.

n

is prime it is a product of one prime, so

S(n)

holds.

Case 2:

n = ab

with

2 \le a, b < n

Case 2:

n

is not prime, so

n = ab

with

1 < a, b < n

(a divisor other than

1

and

n

; the other factor

b = n/a

is also between

1

and

n

by fact 3).

Both

a

and

b

are products of primes, so

n = ab

is a product of primes.

The strong induction hypothesis applies to

a

and to

b

Take the last prime on the left,

p_r

. It divides some

q_j

Uniqueness, by induction on

r

. Suppose

p_1 \cdots p_r = q_1 \cdots q_s

. Then

p_r

divides

q_1 \cdots q_s

, so by Euclid's lemma

p_r \mid q_j

for some

j

p_r = q_j

q_j

is prime, so its only positive divisors are

1

and

q_j

. And

p_r > 1

Then

p_1 \cdots p_{r-1} = q_1 \cdots q_{s-1}

Renumber so that

j = s

, and cancel the common factor

p_r = q_s

from both sides (it is non-zero).

r = 1

, then

s = 1

and the two factorizations are the same single prime.

Case

r = 1

. The left side is now the empty product

1

. A product of one or more primes is at least

2

, so the right side must be empty too:

s = 1

. Then

q_1 = p_1

and we are done.

r \ge 2

, then

r - 1 = s - 1

and

q_1, \dots, q_{s-1}

are

p_1, \dots, p_{r-1}

in some order. Put back

p_r = q_s

r = s

and the lists agree up to order.

Case

r \ge 2

. The left side is at least

2

, so the right side is not empty and

s - 1 \ge 1

. Both sides are now factorizations with

r - 1

and

s - 1

primes, so the induction hypothesis (the theorem for

r - 1

primes on the left) applies.

Worked example

Factor

360

and

84

into primes, and find their gcd and lcm from the factorizations. Check with Euclid.

Solution.

Factor. $360 = 2^3 \cdot 3^2 \cdot 5$ and $84 = 2^2 \cdot 3 \cdot 7$ . Divide out the smallest prime repeatedly: $360 = 8 \cdot 45 = 8 \cdot 9 \cdot 5$ . By the theorem, this is the only factorization.
The gcd takes the smaller exponent of each prime. $2^{\min(3,2)} \cdot 3^{\min(2,1)} \cdot 5^{\min(1,0)} \cdot 7^{\min(0,1)} = 2^2 \cdot 3 = 12$ . A common divisor can use each prime only as often as it appears in both numbers, and uniqueness of factorization is what makes “how often a prime appears” well defined.
The lcm takes the larger exponent. $2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520$ . The least common multiple needs each prime as often as it appears in either number.
Check with Euclid. $360 = 4 \cdot 84 + 24$ , $84 = 3 \cdot 24 + 12$ , $24 = 2 \cdot 12$ . So the gcd is $12$ . Two methods must agree. Also $12 \cdot 2520 = 30240 = 360 \cdot 84$ .

Answer. $\gcd = 12$ and $\operatorname{lcm} = 2520$ . Factorizing is easy for small numbers, but for a 600-digit number nobody knows a fast method. Euclid’s algorithm, on the other hand, is fast for any size. That contrast is the basis of RSA below.

A preview· Preview: unique factorization is special

In the number system $\mathbb Z[\sqrt{-5}]$ of numbers $a + b\sqrt{-5}$ with $a, b$ integers, the number $6$ factors as $2 \cdot 3$ and also as $(1 + \sqrt{-5})(1 - \sqrt{-5})$ , and none of these four factors can be broken down further. Unique factorization fails there. What goes wrong is exactly the step “a prime dividing a product divides a factor”, the content of Euclid’s lemma. Rings where that survives are the subject of MATH 541.

Arithmetic mod n

Definition B

Congruent mod n

Fix a positive integer $n$ (the modulus). Integers $a$ and $b$ are congruent mod $n$ , written $a \equiv b \pmod n$ , if $n \mid (a - b)$ . This is the relation $\sim_n$ of 0.4, which was shown there to be an equivalence relation. Its classes are the residue classes $[a]_n = \{a + nk : k \in \mathbb Z\}$ .

In one line $a \equiv b \pmod n$ means $n$ divides $a - b$ : $a$ and $b$ leave the same remainder on division by $n$ .

Why it existsIt is the precise form of 'the same up to whole multiples of n', the sameness rule behind clock arithmetic.

Theorem B

There are exactly n residue classes

For every integer $a$ there is exactly one $r \in \{0, 1, \dots, n - 1\}$ with $a \equiv r \pmod n$ , namely $r = a \bmod n$ . Consequently the set of classes is $\mathbb Z_n = \{[0], [1], \dots, [n - 1]\}$ , with exactly $n$ elements.

In one lineEvery integer is congruent mod $n$ to exactly one of $0, 1, \dots, n - 1$ , namely its remainder; so there are exactly $n$ classes, and $a \equiv b$ iff $a$ and $b$ have the same remainder.

Why it is trueThe division algorithm gives each integer a remainder in that range, and two different numbers in that range cannot differ by a multiple of $n$ .

ProofHammack 11.3

The idea: Existence from the division algorithm. Uniqueness: two numbers in the range 0 to n minus 1 differ by less than n.

a - r = nq

, a multiple of

n

, and

a \equiv r

Division algorithm:

a = nq + r

with

0 \le r < n

Then

n \mid r - r'

Uniqueness. Suppose

a \equiv r

and

a \equiv r'

with

0 \le r, r' < n

. By symmetry and transitivity (it is an equivalence relation),

r \equiv r'

, that is

n \mid (r - r')

r = r'

\lvert r - r' \rvert < n

, and the only multiple of

n

of size less than

n

0

(fact 3).

The classes

[0], \dots, [n - 1]

are all different and every integer lies in one of them. This matches the ‘sorted into rows’ picture of chapter 0.4.

Equal classes are the same class. Each class contains exactly one remainder.

Now the point of building classes: we want to add and multiply them. Define $[a] + [b] = [a + b]$ and $[a][b] = [ab]$ . Just as for fractions in 0.4, this is only a legitimate definition if the answer does not depend on which representatives $a, b$ you use.

Theorem B

Arithmetic respects congruence

Let $a \equiv a' \pmod n$ and $b \equiv b' \pmod n$ . Then $a + b \equiv a' + b'$ , $a - b \equiv a' - b'$ , and $ab \equiv a'b'$ (mod $n$ ).

In one lineIf $a \equiv a'$ and $b \equiv b'$ (mod $n$ ), then $a + b \equiv a' + b'$ and $ab \equiv a'b'$ ; so addition and multiplication of classes are well defined.

Why it is trueReplacing a number by another in its class only adds multiples of $n$ , and those stay multiples of $n$ after adding or multiplying.

ProofHammack 11.3

The idea: Write a' = a + nk and b' = b + nl and expand. This is exactly the well-definedness check of chapter 0.4.

Write

a' = a + nk

and

b' = b + nl

for integers

k, l

Definition of congruence.

(a' + b') - (a + b) = n(k + l)

, so

a + b \equiv a' + b'

Add the two equations. The difference is a multiple of

n

a'b' - ab = n(al + kb + nkl)

, a multiple of

n

, so

ab \equiv a'b'

Expand

a'b' = (a + nk)(b + nl) = ab + n(al + kb + nkl)

(a' - b') - (a - b) = n(k - l)

, so

a - b \equiv a' - b'

The same bookkeeping for the difference.

So $\mathbb Z_n$ has addition and multiplication, and the usual laws (commutative, associative, distributive) hold because they hold in $\mathbb Z$ : for instance $[a] + [b] = [a + b] = [b + a] = [b] + [a]$ . In practice we write $a$ for $[a]$ , and compute with the smallest representatives. This is the “clock” or “calendar” arithmetic of the picture.

Worked example

Find (a) the last two digits of

7^{2025}

, (b)

2^{100} \bmod 7

, and (c) test whether

4725

is divisible by

9

and

918082

11

Solution.

(a) Find a power that is $1$ . $7^2 = 49$ and $7^4 = 2401 \equiv 1 \pmod{100}$ . If some power is $\equiv 1$ , then powers repeat with that period, so exponents can be reduced.
(a) Reduce the exponent. $2025 = 4 \cdot 506 + 1$ , so $7^{2025} = (7^4)^{506} \cdot 7 \equiv 1^{506} \cdot 7 = 7 \pmod{100}$ . Arithmetic respects congruence, so we may replace $7^4$ by $1$ inside the product.
(a) Answer. The last two digits are $07$ . The remainder mod $100$ is the last two digits.
(b) Same method. $2^3 = 8 \equiv 1 \pmod 7$ and $100 = 3 \cdot 33 + 1$ , so $2^{100} = (2^3)^{33} \cdot 2 \equiv 2 \pmod 7$ . The same pattern: find the power that gives $1$ .
(c) Digit rule for 9. $10 \equiv 1 \pmod 9$ , so $10^k \equiv 1$ and a number with digits $d_k \dots d_1 d_0$ is congruent to $d_k + \dots + d_0$ . For $4725$ : $4 + 7 + 2 + 5 = 18 \equiv 0$ , so $9 \mid 4725$ (indeed $4725 = 9 \cdot 525$ ). Congruence respects sums and products, so each $d \cdot 10^i \equiv d \cdot 1^i$ .
(c) Digit rule for 11. $10 \equiv -1 \pmod{11}$ , so $10^i \equiv (-1)^i$ and a number is congruent to its digits with alternating signs from the right. For $918082$ : $2 - 8 + 0 - 8 + 1 - 9 = -22 \equiv 0$ , so $11 \mid 918082$ (indeed $918082 = 11 \cdot 83462$ ). Same idea with $-1$ in place of $1$ .

Answer. (a) $07$ . (b) $2$ . (c) Both are divisible. In JEE you memorised these digit tests; they are congruences mod $9$ and mod $11$ .

Watch out· You cannot always divide in modular arithmetic

Mod $6$ : $2 \cdot 3 \equiv 2 \cdot 6 \equiv 0$ , but $3 \not\equiv 6$ . So “cancel the $2$ ” gives a wrong answer. Addition and multiplication respect congruence, but cancelling a factor needs that factor to be invertible, which is the next theorem.

Inverses mod n

Definition B

Inverse mod n

An integer $b$ is an inverse of $a$ mod $n$ if $ab \equiv 1 \pmod n$ . We write $a^{-1}$ for it. In the mod 7 table, $3^{-1} = 5$ because $3 \cdot 5 = 15 \equiv 1$ .

In one lineAn inverse of $a$ mod $n$ is a number $b$ with $ab \equiv 1 \pmod n$ ; it lets you divide by $a$ .

Why it existsDividing by $a$ is multiplying by its inverse, so inverses are what make equations $ax \equiv c$ solvable.

Theorem B Hammack 11.3

Inverses mod n exist exactly when coprime

For a positive integer $n$ and an integer $a$ : $a$ has an inverse mod $n$ iff $\gcd(a, n) = 1$ . Any two inverses of $a$ are congruent mod $n$ .

In one line $a$ has an inverse mod $n$ if and only if $\gcd(a, n) = 1$ ; the inverse is unique mod $n$ and is found by the extended Euclidean algorithm.

Why it is trueAn inverse is a solution of $ax + ny = 1$ for $x$ , which Bézout says exists exactly when the gcd is 1.

ProofHammack 11.3

The idea: An inverse b means ab minus 1 is a multiple of n, which is a Bézout equation. Bézout both ways.

ab - nk = 1

(

\Rightarrow

) Suppose

ab \equiv 1

. By the definition of congruence,

ab - 1 = nk

for some integer

k

Hence

d \mid 1

, so

d = 1

and

\gcd(a, n) = 1

Any common divisor

d

a

and

n

divides

ab - nk

(fact 1).

Choose

x, y

with

ax + ny = 1

(

\Leftarrow

) Bézout's identity:

\gcd(a, n) = 1

gives integers

x, y

with

ax + ny = 1

ax \equiv 1 \pmod n

, and

x

is an inverse of

a

Then

ax - 1 = -ny

, a multiple of

n

Any two inverses are congruent mod

n

Uniqueness. If

b

and

b'

are both inverses,

b \equiv b(ab') = (ba)b' \equiv b'

. Each step uses that arithmetic respects congruence.

Quick checkWhich of

4

9

7

has an inverse mod

12

Your answerFind the inverse of

11

mod

26

, as a number from

0

25

Your answerHow many of the classes

[0], [1], \dots, [35]

\mathbb Z_{36}

have an inverse mod

36

Quick checkIn

\mathbb Z_6

you are told

2x \equiv 2y \pmod 6

. What can you conclude?

Worked example

Solve

7x \equiv 4 \pmod{40}

. Also explain why

4x \equiv 1 \pmod 6

has no solution.

Solution.

Check that $7$ is invertible. $\gcd(7, 40) = 1$ . The theorem: invertible iff coprime.
Find the inverse with the extended Euclid. $40 = 5 \cdot 7 + 5$ , $7 = 1 \cdot 5 + 2$ , $5 = 2 \cdot 2 + 1$ . Back-substituting: $1 = 5 - 2 \cdot 2 = 5 - 2(7 - 5) = 3 \cdot 5 - 2 \cdot 7 = 3(40 - 5 \cdot 7) - 2 \cdot 7 = 3 \cdot 40 - 17 \cdot 7$ . This is the Bézout equation $7x + 40y = 1$ with $x = -17$ .
Reduce. $7^{-1} \equiv -17 \equiv 23 \pmod{40}$ . Check: $7 \cdot 23 = 161 = 4 \cdot 40 + 1$ . Add $40$ to land in the range $0$ to $39$ .
Multiply both sides by the inverse. $x \equiv 23 \cdot 4 = 92 \equiv 12 \pmod{40}$ . Multiplying both sides of a congruence by the same number keeps it true, and $23 \cdot 7 \equiv 1$ cancels the coefficient.
Check. $7 \cdot 12 = 84 = 2 \cdot 40 + 4$ . The answer must reproduce the right side.
The second question. $\gcd(4, 6) = 2 \ne 1$ , so $4$ has no inverse mod $6$ . Directly, $4x$ is always even and $1 + 6k$ is always odd, so $4x \equiv 1$ is impossible. A multiple of $4$ and a number of the form $6k + 1$ can never be equal.

Answer. $x \equiv 12 \pmod{40}$ (every $x = 12 + 40t$ works). The equation $4x \equiv 1 \pmod 6$ has no solution.

Corollary B

Division in Z_p

If $p$ is prime and $p \nmid a$ , then $a$ has an inverse mod $p$ .
If $\gcd(c, n) = 1$ and $ca \equiv cb \pmod n$ , then $a \equiv b \pmod n$ .

In one lineIf $p$ is prime, every integer not divisible by $p$ has an inverse mod $p$ ; and if $\gcd(c, n) = 1$ , you may cancel $c$ : $ca \equiv cb$ implies $a \equiv b$ (mod $n$ ).

Why it is trueA prime shares no factor with anything it does not divide, so Bézout applies; and cancelling is multiplying by the inverse.

Proofstandard

The idea: Part 1 is the theorem, since gcd(a, p) divides p so is 1 or p. Part 2 multiplies by the inverse of c.

(1)

\gcd(a, p) = 1

, so

a

has an inverse by the theorem.

\gcd(a, p)

is a positive divisor of

p

, so it is

1

p

. It is not

p

because

p \nmid a

Then

a \equiv (c'c)a = c'(ca) \equiv c'(cb) = (c'c)b \equiv b

(2) Since

\gcd(c, n) = 1

c

has an inverse

c'

with

c'c \equiv 1

. Multiply

ca \equiv cb

c'

So $\mathbb Z_p$ for prime $p$ is a number system where every non-zero element can be divided by, like $\mathbb Q$ or $\mathbb R$ but finite. It is the first finite field, which chapter 2.1 uses as the scalars of a vector space.

Fermat’s little theorem

Theorem B Fermat 1640; Euler

Fermat's little theorem

Let $p$ be a prime. If $p \nmid a$ then $a^{p-1} \equiv 1 \pmod p$ . For every integer $a$ (divisible by $p$ or not), $a^p \equiv a \pmod p$ .

In one lineIf $p$ is prime and $p \nmid a$ , then $a^{p-1} \equiv 1 \pmod p$ ; equivalently $a^p \equiv a \pmod p$ for every integer $a$ .

Why it is trueMultiplying all the non-zero classes by $a$ only shuffles them, so the product of all of them is unchanged, which forces $a^{p-1}$ to be 1.

For $p = 7$ and $a = 3$ the products $3 \cdot 1, 3 \cdot 2, \dots, 3 \cdot 6$ are $3, 6, 9, 12, 15, 18$ , which mod $7$ are $3, 6, 2, 5, 1, 4$ : the numbers $1$ to $6$ again, in a different order (see the row of $3$ in the table above). That is the whole idea.

ProofHammack 11.4

The idea: Show that a, 2a, ..., (p-1)a are the same p - 1 non-zero classes as 1, 2, ..., p-1 in a different order. Multiply them all together and cancel (p-1)!.

None of

a, 2a, \dots, (p - 1)a

\equiv 0 \pmod p

By Euclid's lemma:

p \nmid a

and

p \nmid i

for

1 \le i \le p - 1

, so

p \nmid ia

The classes of

a, 2a, \dots, (p - 1)a

are all different.

Suppose

ia \equiv ja

with

1 \le i, j \le p - 1

. Then

p \mid (i - j)a

. Euclid's lemma gives

p \mid i - j

(since

p \nmid a

i = j

\lvert i - j \rvert < p - 1 \lt p

, so

p \mid i - j

forces

i = j

Hence

a, 2a, \dots, (p - 1)a

are congruent to

1, 2, \dots, p - 1

in some order.

There are

p - 1

distinct non-zero classes, and there are exactly

p - 1

non-zero classes mod

p

(previous theorem). So we get all of them.

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

Multiply all the congruences together (arithmetic respects congruence); the order of multiplication does not matter.

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

(p - 1)!

is a product of numbers not divisible by

p

, so by Euclid's lemma

p \nmid (p-1)!

, thus

\gcd((p-1)!, p) = 1

and we may cancel it (the corollary).

Therefore

a^p \equiv a \pmod p

for all

a

Multiply by

a

. If

p \mid a

, both sides of

a^p \equiv a

are

\equiv 0

Quick checkWhat is

7^{100} \bmod 11

Your answerWhat is

3^{100} \bmod 7

(a number from

0

6

Worked example

Compute

5^{117} \bmod 11

, and find

3^{-1} \bmod 7

using Fermat.

Solution.

Use Fermat. $11$ is prime and $11 \nmid 5$ , so $5^{10} \equiv 1 \pmod{11}$ . The exponent $p - 1 = 10$ is the period of the powers.
Reduce the exponent mod 10. $117 = 11 \cdot 10 + 7$ , so $5^{117} = (5^{10})^{11} \cdot 5^7 \equiv 5^7$ . Replace $5^{10}$ by $1$ .
Compute $5^7$ by squaring. $5^2 = 25 \equiv 3$ , $5^4 \equiv 3^2 = 9$ , so $5^7 = 5^4 \cdot 5^2 \cdot 5 \equiv 9 \cdot 3 \cdot 5 = 135 = 12 \cdot 11 + 3$ . $7 = 4 + 2 + 1$ , and each power is reduced mod $11$ as we go.
The inverse. $3^6 \equiv 1 \pmod 7$ , so $3 \cdot 3^5 \equiv 1$ and $3^{-1} \equiv 3^5 = 243 = 34 \cdot 7 + 5 \equiv 5$ . In general $a^{-1} \equiv a^{p-2} \pmod p$ .

Answer. $5^{117} \equiv 3 \pmod{11}$ , and $3^{-1} \equiv 5 \pmod 7$ (check: $3 \cdot 5 = 15 \equiv 1$ ).

Watch out· Fermat's theorem needs p prime and p not dividing a

The converse is false. The number $341 = 11 \cdot 31$ is composite, yet $2^{340} \equiv 1 \pmod{341}$ . Such numbers are why primality tests use more than Fermat. Also, an exponent may be reduced mod $p - 1$ only when $p$ does not divide the base. The base itself is reduced mod $p$ .

Why RSA works

RSA needs one more step: Fermat’s theorem for a product of two primes.

Theorem B

RSA decryption works

Let $p \ne q$ be primes, $n = pq$ , and $e, d$ positive integers with $ed = 1 + k(p-1)(q-1)$ for some integer $k \ge 0$ . Then $m^{ed} \equiv m \pmod n$ for every integer $m$ .

In one lineIf $n = pq$ for distinct primes and $ed \equiv 1 \pmod{(p-1)(q-1)}$ , then $(m^e)^d \equiv m \pmod n$ for every integer $m$ .

Why it is trueFermat's theorem shows $m^{ed} \equiv m$ separately mod $p$ and mod $q$ , and two distinct primes dividing a number means their product does.

ProofRivest, Shamir, Adleman 1978

The idea: Show p divides m^(ed) - m and q divides it too, using Fermat; then pq divides it by Euclid's lemma.

Mod

p

, first suppose

p \mid m

. Then both

m^{ed}

and

m

are

\equiv 0

Case

p \mid m

: then

p

divides

m^{ed}

and

m

, so

p \mid m^{ed} - m

p \nmid m

, then

m^{ed} = m \cdot (m^{p-1})^{k(q-1)} \equiv m \pmod p

Case

p \nmid m

: Fermat gives

m^{p-1} \equiv 1

. Then

m^{ed} = m \cdot (m^{p-1})^{k(q-1)} \equiv m \cdot 1 = m

Likewise

m^{ed} \equiv m \pmod q

The identical argument with

q

in place of

p

, using

ed = 1 + k(q-1)(p-1)

p \mid m^{ed} - m

and

q \mid m^{ed} - m

, and hence

pq \mid m^{ed} - m

Write

m^{ed} - m = pt

. Then

q \mid pt

. The prime

q

does not divide the different prime

p

, so Euclid's lemma gives

q \mid t

m^{ed} \equiv m \pmod n

That is the definition of congruence mod

n

Where this came from· Gauss, Diffie and Hellman, and RSA

Gauss’s Disquisitiones Arithmeticae (1801) gave the notation $a \equiv b \pmod n$ , treated computing with remainders systematically, and stated and proved explicitly that factorization into primes is unique. For two centuries this was pure mathematics. In 1976 Whitfield Diffie and Martin Hellman asked whether two people could agree on a secret over a public channel, and in 1977 Ron Rivest, Adi Shamir and Leonard Adleman at MIT found the system now called RSA (published in 1978), which turns the question into the gap between multiplying primes, which is fast, and factoring their product, which is not known to be. Clifford Cocks at the British agency GCHQ had found an equivalent system in 1973; it stayed secret until 1997.

Examples and non-examples

The worked examples above cover each skill in the problem list: dividing with remainder, Euclid’s algorithm, the extended algorithm, linear equations in integers, unique factorization, computing mod $n$ , inverses, Fermat, and RSA. Three more short ones fix the ideas: zero divisors, check digits, and a proof that uses unique factorization.

Worked example

[3] + [4] = [1]

\mathbb Z_6

? Find all pairs

(a, b)

of non-zero classes in

\mathbb Z_6

with

ab = 0

Solution.

The sum. $3 + 4 = 7 = 6 + 1$ , so $[3] + [4] = [1]$ in $\mathbb Z_6$ . Reduce the sum mod $6$ .
Hunt for zero products. A product $ab \equiv 0 \pmod 6$ means $6 \mid ab$ . Try $a = 2$ : $2 \cdot 3 = 6$ , so $[2][3] = 0$ . Try $a = 4$ : $4 \cdot 3 = 12$ , so $[4][3] = 0$ . Also $[2][3] = [3][2] = 0$ and $[3][4] = 0$ . Look for pairs whose prime factors $2$ and $3$ are split between them.
Sanity check with the table. In the mod 6 table, the zeros are at $(2,3), (3,2), (3,4), (4,3)$ . The table agrees.

Answer. Yes. The non-zero pairs with product zero are $\{2, 3\}$ and $\{3, 4\}$ (in either order). These “zero divisors” exist exactly because $6$ is not prime, which is why $\mathbb Z_6$ cannot divide.

Worked example

The first twelve digits of an ISBN-13 are

978140289462

. Find the check digit, and say whether

9780131103627

is a valid ISBN-13.

The rule: multiply the digits alternately by $1$ and $3$ , starting with $1$ , and add. A valid ISBN-13 has total $\equiv 0 \pmod{10}$ . The last digit is chosen to make that true.

Solution.

Weight the first twelve digits. $9\cdot1 + 7\cdot3 + 8\cdot1 + 1\cdot3 + 4\cdot1 + 0\cdot3 + 2\cdot1 + 8\cdot3 + 9\cdot1 + 4\cdot3 + 6\cdot1 + 2\cdot3$ . The weights run $1, 3, 1, 3, \dots$ across the twelve digits, and the thirteenth digit has weight $1$ .
Add. $9 + 21 + 8 + 3 + 4 + 0 + 2 + 24 + 9 + 12 + 6 + 6 = 104$ . Plain arithmetic.
Choose the check digit $c$ . We need $104 + c \equiv 0 \pmod{10}$ , and $104 \equiv 4$ , so $c \equiv -4 \equiv 6$ . The check digit is the number from $0$ to $9$ that completes the congruence.
Test the second number. Its first twelve digits $978013110362$ give $9 + 21 + 8 + 0 + 1 + 9 + 1 + 3 + 0 + 9 + 6 + 6 = 73$ , and adding the last digit $7$ with weight $1$ gives $80 \equiv 0$ . The full total, including the check digit, must be a multiple of $10$ .

Answer. The check digit is $6$ , and $9780131103627$ is valid. Changing any single digit changes the total by $w \cdot e$ with $w \in \{1, 3\}$ , which is never $\equiv 0 \pmod{10}$ because $1$ and $3$ are invertible mod $10$ , so every single-digit typing error is caught.

Worked example Euclid IX.20

Prove that there are infinitely many primes.

Solution. The plan: assume there are only finitely many, build a number that no prime on the list can divide, and use the fundamental theorem to find a contradiction.

Assume the opposite. Suppose the primes are exactly $p_1, p_2, \dots, p_k$ . Proof by contradiction (0.2): we assume the negation of the claim.
Build a number. Let $N = p_1 p_2 \cdots p_k + 1$ . Then $N > 1$ . Every $p_i$ divides the product, so dividing $N$ by $p_i$ always leaves remainder $1$ .
Find a prime divisor. By the fundamental theorem $N$ is a product of primes, so some prime $p$ divides $N$ . Since the list contains all primes, $p = p_i$ for some $i$ . Existence of a prime factorization, applied to $N$ .
Get the contradiction. Then $p_i \mid N$ and $p_i \mid p_1 \cdots p_k$ , so $p_i \mid N - p_1 \cdots p_k = 1$ . But no prime divides $1$ . Fact 1: a divisor of two numbers divides their difference. A prime is greater than $1$ , and a divisor of $1$ has size at most $1$ (fact 3).

Answer. The assumption is impossible, so there are infinitely many primes. The proof does not claim that $N$ itself is prime.

Worked example

Solve the system

x \equiv 3 \pmod 4

and

x \equiv 2 \pmod 7

Solution.

Check the moduli are coprime. $\gcd(4, 7) = 1$ . Then Bézout gives $4u + 7v = 1$ , which is the tool for gluing the two conditions.
Find $u, v$ . $4 \cdot 2 + 7 \cdot (-1) = 1$ , so $u = 2$ , $v = -1$ . Extended Euclid, or just trial for numbers this small.
Build a solution. Take $x_0 = 3 \cdot 7 \cdot (-1) + 2 \cdot 4 \cdot 2 = -21 + 16 = -5$ . The term $7v \equiv 1 \pmod 4$ and $4u \equiv 1 \pmod 7$ . So $7v$ acts like $1$ mod $4$ and like $0$ mod $7$ , and $4u$ acts like $0$ mod $4$ and like $1$ mod $7$ . The combination $3 \cdot (7v) + 2 \cdot (4u)$ is then $3$ mod $4$ and $2$ mod $7$ .
Reduce. $-5 + 28 = 23$ . Adding the product of the moduli, $28$ , changes neither congruence.
Check. $23 = 5 \cdot 4 + 3$ and $23 = 3 \cdot 7 + 2$ . The answer must reproduce both remainders.

Answer. $x \equiv 23 \pmod{28}$ , and every solution has this form.

Where it is used

Used inside maths· Inside maths: fields, groups, and the Euclidean algorithm for polynomials

$\mathbb Z_p$ for a prime $p$ is a finite field, so you can do linear algebra over it: vector spaces, bases, and determinants all work with scalars from $\mathbb Z_p$ (chapter 2.1 uses fields). The invertible classes mod $n$ form a group under multiplication, with $\varphi(n)$ elements (the number of $k$ from $1$ to $n$ with $\gcd(k, n) = 1$ ). Lagrange’s theorem (MATH 541) then gives Euler’s generalisation of Fermat: $a^{\varphi(n)} \equiv 1 \pmod n$ when $\gcd(a, n) = 1$ . The same Euclid’s-algorithm-and-Bézout argument works for polynomials, where the remainder has smaller degree, and gives the gcd of two polynomials: this is the generalisation that carries Bézout’s name.

Used in the real world· Real systems: RSA encryption, check digits, and hash tables

RSA with real numbers (tiny). Take the primes $p = 5$ and $q = 11$ . Then $n = pq = 55$ and $(p-1)(q-1) = 4 \cdot 10 = 40$ . Choose $e = 3$ , which is coprime to $40$ . The private exponent $d$ is the inverse of $3$ mod $40$ . Publish $(n, e) = (55, 3)$ and keep $d$ secret.

Your answerTake the RSA primes

p = 7

and

q = 11

with public exponent

e = 7

. What is the private exponent

d

, as the smallest positive number with

ed \equiv 1 \pmod{(p-1)(q-1)}

Real RSA uses primes of about 1024 bits each, so $n$ has about 617 digits, and a common public exponent is $e = 65\,537$ . Here anyone can factor $55 = 5 \cdot 11$ at once, compute $40$ , and invert $3$ . With a 617-digit $n$ nobody knows how to factor it in reasonable time, while Euclid’s algorithm and fast squaring keep encryption and decryption quick. (Real systems also pad messages; raw RSA as shown is for understanding only.)

Check digits. The last digit of a code is chosen to make a congruence hold, so typing errors break it.

ISBN-13 (books): multiply the digits alternately by $1$ and $3$ and add; the total must be $\equiv 0 \pmod{10}$ . For $978\text{-}0\text{-}306\text{-}40615\text{-}7$ the sum is $9 + 21 + 8 + 0 + 3 + 0 + 6 + 12 + 0 + 18 + 1 + 15 + 7 = 100$ . A single wrong digit changes the sum by $w \cdot e$ with weight $w \in \{1, 3\}$ and error $0 < \lvert e \rvert \le 9$ . Both weights are coprime to $10$ , so they are invertible, and $we \equiv 0$ would force $e \equiv 0 \pmod{10}$ , which is impossible. So every single-digit error is caught. Swapping two adjacent digits $x, y$ changes the sum by $2(x - y)$ , which is $\equiv 0$ only when $x - y = \pm 5$ , so swaps like $0 \leftrightarrow 5$ slip through.
ISBN-10: weights $10, 9, \dots, 1$ and modulus $11$ . For $0\text{-}306\text{-}40615\text{-}2$ the sum is $132 = 11 \cdot 12$ . Because $11$ is prime, every weight is invertible and the difference of two different digits is never a multiple of $11$ , so every single-digit error and every swap of adjacent different digits is caught. (The check digit may be $10$ , written X.)
UPC-A (barcodes): weights $3, 1, 3, 1, \dots$ on the 12 digits, total $\equiv 0 \pmod{10}$ . For $036000291452$ : $3(0 + 6 + 0 + 2 + 1 + 5) + (3 + 0 + 0 + 9 + 4 + 2) = 42 + 18 = 60$ .
Luhn (credit cards, devised by Hans Peter Luhn of IBM in the 1950s): from the right, double every second digit (subtracting $9$ if the result exceeds $9$ ), add everything, and require a multiple of $10$ . For $79927398713$ the processed digits are $7, 9, 9, 4, 7, 6, 9, 7, 7, 2, 3$ with sum $70$ . The doubling map sends the digits $0, 1, \dots, 9$ to $0, 2, 4, 6, 8, 1, 3, 5, 7, 9$ , a shuffle of the digits, so changing one digit always changes the sum mod $10$ . It catches every adjacent swap except $09 \leftrightarrow 90$ . (Aadhaar numbers use a different check, the Verhoeff scheme, built from the symmetries of a pentagon, which catches all adjacent swaps; its algebra is a group, seen in MATH 541.)

Hash tables. A hash function $h(k) = k \bmod m$ puts key $k$ in one of $m$ buckets. Take the ten keys $100, 110, \dots, 190$ . With $m = 10$ every key lands in bucket $0$ , since each is a multiple of $10$ . With $m = 11$ they land in buckets $1, 0, 10, 9, 8, 7, 6, 5, 4, 3$ , all different, because $10$ is coprime to $11$ . In general, if every key is a multiple of $g$ and $g$ divides $m$ , only $m / g$ of the buckets are ever used, which is one reason table sizes are often chosen prime. And by the pigeonhole principle of 0.3 no hash into $m$ buckets can avoid collisions once there are more than $m$ keys.

Traps

Watch out· Remainders are never negative

$-7 \bmod 3 = 2$ , not $-1$ . Some programming languages (C, Java) return $-1$ for the remainder of $-7 / 3$ and others (Python) return $2$ . In mathematics the remainder is in $0, \dots, n - 1$ . The two are congruent mod $3$ , so either is fine inside a congruence, but they are different answers to “what is the remainder”.

Watch out· 'mod' is used for two different things

$a \bmod n$ is a number, the remainder of $a$ . $a \equiv b \pmod n$ is a statement about $a$ and $b$ . We have $17 \equiv 2 \pmod 5$ and $17 \bmod 5 = 2$ , but $17 \bmod 5 = 2$ is an equation between numbers while the first line is a relation.

Watch out· Cancelling needs a unit

You may cancel $c$ from $ca \equiv cb \pmod n$ only when $\gcd(c, n) = 1$ . In general you can only cancel to $a \equiv b \pmod{n / \gcd(c, n)}$ . For example $2 \cdot 1 \equiv 2 \cdot 4 \pmod 6$ gives $1 \equiv 4 \pmod 3$ , which is true, not $1 \equiv 4 \pmod 6$ .

Watch out· Reducing exponents

Exponents reduce mod $p - 1$ (when $p \nmid a$ ), not mod $p$ : $a^{p-1} \equiv 1$ , so $a^{k}$ depends on $k \bmod (p-1)$ . For $p = 7$ : $3^{8} \equiv 3^{2} = 9 \equiv 2$ , not $3^{8 \bmod 7} = 3^1$ .

Watch out· The number 1 is not prime

The integer $1$ is not prime, and negative numbers are not called prime in this book. A prime has exactly two positive divisors, which is why $1$ (one divisor) is excluded. Without this, unique factorization would fail ( $6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3$ ).

Problems

check

Find the quotient and remainder when $1000$ is divided by $7$ , and when $-45$ is divided by $8$ .

Solution

$1000 = 7 \cdot 142 + 6$ , so $q = 142$ , $r = 6$ . $-45 = 8 \cdot (-6) + 3$ , so $q = -6$ , $r = 3$ (check: $-48 + 3 = -45$ ).

check

Compute $\gcd(126, 84)$ by Euclid’s algorithm, and $\gcd(91, 35)$ .

Solution

$126 = 1 \cdot 84 + 42$ , $84 = 2 \cdot 42 + 0$ , so $\gcd(126, 84) = 42$ . $91 = 2 \cdot 35 + 21$ , $35 = 1 \cdot 21 + 14$ , $21 = 1 \cdot 14 + 7$ , $14 = 2 \cdot 7$ , so $\gcd(91, 35) = 7$ .

check

Does $2x \equiv 3 \pmod 6$ have a solution? Does $5x \equiv 1 \pmod{12}$ ?

Solution

$\gcd(2, 6) = 2 \nmid 3$ , so the first has no solution ( $2x - 3$ is odd, never a multiple of $6$ ). $\gcd(5, 12) = 1$ , and $5 \cdot 5 = 25 = 2 \cdot 12 + 1$ , so $x \equiv 5$ is a solution.

checkCS 240

Find $3^{50} \bmod 5$ and the last digit of $7^{100}$ .

Solution

$3^4 = 81 \equiv 1 \pmod 5$ , $50 = 4 \cdot 12 + 2$ , so $3^{50} \equiv 3^2 = 9 \equiv 4$ . For the last digit take mod $10$ : $7^4 = 2401 \equiv 1 \pmod{10}$ and $100 = 4 \cdot 25$ , so $7^{100} \equiv 1$ . The last digit is $1$ .

use

Find integers $x, y$ with $91x + 35y = 7$ .

Solution

From the Euclid lines $91 = 2 \cdot 35 + 21$ , $35 = 1 \cdot 21 + 14$ , $21 = 1 \cdot 14 + 7$ : $7 = 21 - 14 = 21 - (35 - 21) = 2 \cdot 21 - 35 = 2(91 - 2 \cdot 35) - 35 = 2 \cdot 91 - 5 \cdot 35$ . So $x = 2$ , $y = -5$ . Check: $182 - 175 = 7$ .

use

Solve $17x \equiv 5 \pmod{43}$ .

Solution

$\gcd(17, 43) = 1$ . Euclid: $43 = 2 \cdot 17 + 9$ , $17 = 1 \cdot 9 + 8$ , $9 = 1 \cdot 8 + 1$ . Back: $1 = 9 - 8 = 9 - (17 - 9) = 2 \cdot 9 - 17 = 2(43 - 2 \cdot 17) - 17 = 2 \cdot 43 - 5 \cdot 17$ . So $17^{-1} \equiv -5 \equiv 38$ . Then $x \equiv 5 \cdot 38 = 190 = 4 \cdot 43 + 18 \equiv 18$ . Check: $17 \cdot 18 = 306 = 7 \cdot 43 + 5$ .

use

Use Fermat’s theorem to find $2^{100} \bmod 13$ .

Solution

$13$ is prime and $13 \nmid 2$ , so $2^{12} \equiv 1 \pmod{13}$ . $100 = 8 \cdot 12 + 4$ , so $2^{100} \equiv 2^4 = 16 \equiv 3$ .

use

RSA with $p = 7$ , $q = 13$ , $e = 5$ . Find $n$ , the private exponent $d$ , and encrypt $m = 10$ . Check that decryption returns $10$ .

Solution

$n = 91$ and $(p-1)(q-1) = 6 \cdot 12 = 72$ . $\gcd(5, 72) = 1$ . Find $d$ : $72 = 14 \cdot 5 + 2$ , $5 = 2 \cdot 2 + 1$ , so $1 = 5 - 2 \cdot 2 = 5 - 2(72 - 14 \cdot 5) = 29 \cdot 5 - 2 \cdot 72$ , so $d = 29$ ( $5 \cdot 29 = 145 = 2 \cdot 72 + 1$ ). Encrypt: $10^5 = 100000 = 1098 \cdot 91 + 82$ , so $c = 82$ . Decrypt: $82^{29} \bmod 91 = 10$ (check by repeated squaring, or by Fermat mod $7$ and mod $13$ separately, as in the proof).

use

Is the ISBN-13 $9780306406158$ valid? What should its last digit be?

Solution

Weights $1, 3, 1, 3, \dots$ on the first twelve digits $9, 7, 8, 0, 3, 0, 6, 4, 0, 6, 1, 5$ give $9 + 21 + 8 + 0 + 3 + 0 + 6 + 12 + 0 + 18 + 1 + 15 = 93$ . The check digit must make the total a multiple of $10$ , so it is $7$ . The last digit $8$ gives $101$ , which is not, so the number is invalid.

proveHammack 5.4

Prove that $\gcd(a, b) = \gcd(a, b + ka)$ for every integer $k$ (with $a$ and $b$ not both zero).

Solution

Let $d$ divide $a$ and $b$ . Then $d$ divides $b + ka$ by fact 1, so every common divisor of $(a, b)$ is a common divisor of $(a, b + ka)$ . Conversely if $d$ divides $a$ and $b + ka$ then $d$ divides $(b + ka) - ka = b$ . So the two pairs have the same common divisors and the same greatest one.

prove

Prove: if $\gcd(a, n) = 1$ and $\gcd(b, n) = 1$ then $\gcd(ab, n) = 1$ .

Solution

By Bézout, $ax + ny = 1$ and $bu + nv = 1$ for integers $x, y, u, v$ . Multiply: $1 = (ax + ny)(bu + nv) = ab(xu) + n(axv + ybu + nyv)$ . This is a combination of $ab$ and $n$ equal to $1$ , so any common divisor of $ab$ and $n$ divides $1$ , and $\gcd(ab, n) = 1$ .

prove

Prove: if $a \mid c$ , $b \mid c$ and $\gcd(a, b) = 1$ , then $ab \mid c$ . Is it true without the coprime condition?

Solution

Write $c = ak$ and $c = bl$ , and take $ax + by = 1$ (Bézout). Then $c = cax + cby = (bl)ax + (ak)by = ab(lx + ky)$ , so $ab \mid c$ . Without coprimality it fails: $6 \mid 12$ and $4 \mid 12$ but $24 \nmid 12$ .

proveEuclid IX.20

Prove that for every positive integer $n$ there is a prime $p > n$ . (Look at $n! + 1$ .)

Solution

The number $N = n! + 1$ is greater than $1$ , so it has a prime divisor $p$ by the fundamental theorem. Suppose $p \le n$ . Then $p$ is one of the factors $1, 2, \dots, n$ of $n!$ , so $p \mid n!$ . Also $p \mid N$ , so $p \mid N - n! = 1$ by fact 1, which is impossible for a prime. So $p > n$ . (Hence there is no largest prime.)

prove

Prove: $\gcd(a, b) \cdot \operatorname{lcm}(a, b) = ab$ for positive integers, using the prime factorizations of $a$ and $b$ .

Solution

Write $a = \prod p_i^{s_i}$ and $b = \prod p_i^{t_i}$ over the same list of primes, allowing exponents $0$ . By unique factorization the gcd is $\prod p_i^{\min(s_i, t_i)}$ and the lcm is $\prod p_i^{\max(s_i, t_i)}$ (a common divisor can use each prime at most as often as it appears in both, a common multiple at least as often as in either). For each $i$ , $\min(s_i, t_i) + \max(s_i, t_i) = s_i + t_i$ , so the product of gcd and lcm has exponent $s_i + t_i$ on $p_i$ , which is the exponent of $ab$ . Example: $12 \cdot 2520 = 30240 = 360 \cdot 84$ .

stretch

Prove $\gcd(2^m - 1,\ 2^n - 1) = 2^{\gcd(m, n)} - 1$ , and check it for $m = 12$ , $n = 18$ .

Solution

Let $m = nq + r$ with $0 \le r < n$ . Then $2^m - 1 = 2^r(2^{nq} - 1) + (2^r - 1)$ . Since $x - 1$ divides $x^q - 1$ (geometric sum), $2^n - 1$ divides $2^{nq} - 1$ , so $2^m - 1 = (2^n - 1)t + (2^r - 1)$ for an integer $t$ . By Euclid’s reduction step, $\gcd(2^m - 1, 2^n - 1) = \gcd(2^n - 1, 2^r - 1)$ . This is Euclid’s algorithm run on the exponents $m, n, r, \dots$ , so it ends with $\gcd(2^g - 1, 2^0 - 1) = \gcd(2^g - 1, 0) = 2^g - 1$ , where $g = \gcd(m, n)$ is the last non-zero exponent. For $m = 12$ , $n = 18$ : $g = 6$ and $2^6 - 1 = 63$ . Direct: $2^{12} - 1 = 4095 = 63 \cdot 65$ and $2^{18} - 1 = 262143 = 63 \cdot 4161$ , with $\gcd(65, 4161) = 1$ .

stretchChinese remainder theorem

Let $\gcd(m, n) = 1$ . Prove that for any integers $a, b$ the system $x \equiv a \pmod m$ , $x \equiv b \pmod n$ has a solution, and that it is unique mod $mn$ . Solve $x \equiv 2 \pmod 3$ , $x \equiv 3 \pmod 5$ .

Solution

By Bézout, $mu + nv = 1$ for some integers $u, v$ . Put $x_0 = a n v + b m u$ . Mod $m$ : $nv = 1 - mu \equiv 1$ , and $bmu \equiv 0$ , so $x_0 \equiv a$ . Mod $n$ : $mu = 1 - nv \equiv 1$ and $anv \equiv 0$ , so $x_0 \equiv b$ . Uniqueness: if $x$ and $x'$ are both solutions then $m \mid x - x'$ and $n \mid x - x'$ , so $mn \mid x - x'$ by the coprime problem above. For $m = 3$ , $n = 5$ : $3 \cdot 2 + 5 \cdot (-1) = 1$ , so $u = 2$ , $v = -1$ and $x_0 = 2 \cdot 5 \cdot (-1) + 3 \cdot 3 \cdot 2 = -10 + 18 = 8$ . Check: $8 = 3 \cdot 2 + 2 = 5 + 3$ . All solutions are $x \equiv 8 \pmod{15}$ .

Summary

Division algorithm: for $b > 0$ , $a = bq + r$ with $0 \le r < b$ , $q$ and $r$ unique (proved by well-ordering). Remainders are never negative.
Euclid’s algorithm replaces $(a, b)$ by $(b, r)$ without changing the gcd, and ends at the last non-zero remainder.
Bézout: $\gcd(a, b) = ax + by$ for some integers $x, y$ (the extended Euclid finds them). Hence $ax + by = c$ is solvable iff $\gcd(a, b) \mid c$ .
Euclid’s lemma: a prime dividing a product divides a factor. It gives unique factorization into primes.
$a \equiv b \pmod n$ means $n \mid a - b$ . It is an equivalence relation with exactly $n$ classes, and $+$ and $\times$ on classes are well defined, as for fractions in 0.4.
Inverses: $a$ has an inverse mod $n$ iff $\gcd(a, n) = 1$ ; so you can divide mod a prime, and cancel a factor only if it is coprime to the modulus.
Fermat: $a^{p-1} \equiv 1 \pmod p$ for $p \nmid a$ . It makes RSA work: encryption is $m^e$ , decryption $c^d$ , with $ed \equiv 1 \pmod{(p-1)(q-1)}$ , and the security is the difficulty of factoring $n = pq$ .
Check digits (ISBN, UPC, Luhn) and hash tables are congruences in disguise; their strengths and weaknesses come from which weights and moduli are invertible.

Watch and read

The same ideas explained by someone else. Use these when an explanation here does not land.

The picture

The idea, in words

Definitions and theorems

Division with remainder

Division algorithm

Divisibility

Divides

Divisibility facts

The greatest common divisor

Gcd

Euclid's reduction step

Euclid's algorithm

Bézout’s identity

Bézout's identity

Linear combinations of two integers

Primes and unique factorization

Prime

Euclid's lemma

Fundamental theorem of arithmetic

Arithmetic mod n

Congruent mod n

There are exactly n residue classes

Arithmetic respects congruence

Inverses mod n

Inverse mod n

Inverses mod n exist exactly when coprime

Division in Z_p

Fermat’s little theorem

Fermat's little theorem

Why RSA works

RSA decryption works

Examples and non-examples

Where it is used

Traps

Problems

Summary

Watch and read

Where this sits

Comes from

Leads to

Same idea elsewhere