You have 1,071 identical tiles and want to lay them in a complete rectangle with no gaps and none left over. Which rectangle shapes work? You have 7 days of logs and want them bucketed by weekday: which bucket does day 1,000 fall in? A loop has to process items in batches of 64. How many full batches are there, and how many items are left over?

All three questions ask the same thing: what happens when one whole number is divided by another and we refuse to leave the integers. There are no fractions and no decimals. There is a whole-number quotient and a whole-number remainder.

Think of dividing 23 by 5 as dealing 23 cards into piles of 5. You make 4 complete piles and 3 cards are left over:

The leftover is always smaller than the pile size. If it weren’t, you could make one more pile. That simple fact is what everything in this chapter rests on.

The card-dealing picture becomes a theorem. (The name is old. It is a statement that a quotient and remainder exist, not a step-by-step algorithm.)

The condition \(0 \le r < b\) is what makes the answer unique. Without it, \(23 = 3 \cdot 5 + 8\) would also be a valid split. With it, there is only one choice: take \(q\) to be the largest integer with \(qb \le a\). That works for negative \(a\) too:

Note that the quotient is \(-5\), not \(-4\). Since \((-4)\cdot 5 = -20\), that choice would give remainder \(-3\), which breaks \(0 \le r\). Programming languages disagree about this case. Section 23.7 sorts out who does what.

Three facts follow directly from the definition. Each one is a one-line argument, so here they are:

Combining the first two: if \(d\) divides both \(a\) and \(b\), then \(d\) divides every integer combination \(xa + yb\). We’ll lean on this sentence repeatedly. It is the engine behind both the Euclidean algorithm and Bézout’s identity.

Which rectangles can 1,071 tiles make? A rectangle with sides \(w \times h\) uses \(wh\) tiles, so we need the divisors of 1,071. Divide by small numbers:

Each divisor picks 0, 1 or 2 threes, 0 or 1 seven, and 0 or 1 seventeen, so there are \(3 \cdot 2 \cdot 2 = 12\) divisors: 1, 3, 7, 9, 17, 21, 51, 63, 119, 153, 357, 1071. That gives six rectangle shapes up to rotation: \(1\times1071\), \(3\times357\), \(7\times153\), \(9\times119\), \(17\times63\) and \(21\times51\).

Day 1,000. If day 0 is a Monday, then day 1,000 lands on weekday \(1000 \bmod 7\):

six days after Monday, a Sunday.

Some numbers break into smaller factors: \(1071 = 3^2 \cdot 7 \cdot 17\). Some don’t: 17 has no divisors except 1 and itself. Is there a finite list of these "atoms", or do they go on forever? And when you break a number into atoms, can two different people end up with two different answers?

It has two halves, and they deserve different amounts of attention.

Existence is the easy half. Take \(n\). If it is prime, you’re done. If not, split it as \(n = ab\) with both factors smaller, and keep splitting. The numbers shrink every time, so the process must stop, and when it stops every piece is prime. If you sketch the splits you get a factor tree:

Uniqueness is the deep half. If you’d started with \(360 = 8 \cdot 45\), could you have finished with different primes? The answer is no, but the reason needs a fact we don’t have yet, Euclid’s lemma (if a prime divides a product, it divides one of the factors). We’ll prove that lemma in Section 23.5 using the Euclidean algorithm. Uniqueness then follows quickly. Two factorizations of the same number share any prime \(p\) that appears in the first, because \(p\) divides the product on the second side and so must divide (that is, equal) one of its primes. Cancel it from both sides and repeat.

To factor \(n\), try dividing by 2, 3, 4, 5, …​ in turn. Whenever a trial divisor \(d\) works, divide it out as many times as it goes and carry on with what’s left. Two observations make this efficient enough for small numbers.

Worked example: is 391 prime? \(\sqrt{391} \approx 19.8\), so try primes up to 19. It isn’t even. Its digit sum is 13, so 3 fails. It doesn’t end in 0 or 5. \(391 = 7 \cdot 55 + 6\), so 7 fails. For 11, the alternating sum \(1 - 9 + 3 = -5\) is not a multiple of 11. \(391 = 13 \cdot 30 + 1\), so 13 fails. Then \(391 = 17 \cdot 23\). Composite. Numbers like this, a product of two primes of similar size, are exactly the kind RSA uses, just millions of times larger. Try it: Is 391 prime? Step through; Factorise 391.

Infinitely many. Euclid’s proof, about 300 BCE, is one of the first proofs anyone should see, and it appears in full in Chapter 22. In brief: given any finite list of primes, multiply them all together and add 1. The result leaves remainder 1 when divided by each listed prime, so its prime factors are all new. No finite list can be complete.

The primes also thin out. Among the first 100 integers, 25 are prime. Among the first million, 78,498 are. The prime number theorem (1896) says the number of primes up to \(n\) is roughly \(n / \ln n\). For \(n = 10^6\) that estimate gives about 72,382, which is low by 8% but captures the trend. Near a 300-digit number, roughly one integer in 690 is prime. That is plenty for RSA, which needs to find big primes quickly.

Everyday: common denominators. To add \(\tfrac{5}{12} + \tfrac{7}{18}\), factor: \(12 = 2^2 \cdot 3\) and \(18 = 2 \cdot 3^2\). The least common denominator takes the highest power of each prime, \(2^2 \cdot 3^2 = 36\), so the sum is \(\tfrac{15}{36} + \tfrac{14}{36} = \tfrac{29}{36}\). Uniqueness of factorization is what makes "highest power of each prime" a well-defined recipe.

Biology: prime-numbered life cycles. Periodical cicadas in North America spend 13 or 17 years underground and then emerge together in their billions. One leading explanation is arithmetic. A predator whose population peaks every 2, 3, 4, 5 or 6 years coincides with a 17-year brood only every \(\operatorname{lcm}\) of the two periods: 34, 51, 68, 85 or 102 years. A 12-year cicada would meet the 2-, 3-, 4- and 6-year predators every single emergence.

Engineering: hunting-tooth gears. A car’s final drive often pairs an 11-tooth pinion with a 41-tooth ring gear (ratio \(41/11 \approx 3.73\)). Because 41 is prime, the two counts share no factor, so a given pinion tooth meets every one of the 41 ring-gear teeth before any pairing repeats, after \(11 \times 41 = 451\) tooth engagements. Any manufacturing flaw on one tooth is spread over the whole gear instead of grinding the same spot.

Computing. Public-key cryptography rests on the asymmetry between multiplying two large primes (microseconds) and factoring the product (beyond any known classical computer for 2,048-bit numbers); Section 23.12 runs the numbers.

Trial division tests one number at a time. Often you want all the primes up to some bound: to precompute a lookup table, to factor many small numbers, or to generate test data. Testing each of a million numbers separately repeats a lot of work. Can we share it?

Turn the question around. Instead of asking "what divides this number?", ask "which numbers does this prime knock out?" Write down 2 through \(n\). The first number, 2, is prime, so cross out every multiple of 2 after it. The next number not crossed out, 3, must be prime, because nothing smaller divides it. Cross out its multiples. Then 5, then 7, and so on. Whatever survives is prime.

A number survives exactly when no smaller prime divides it, and that is the definition of prime. Two refinements matter. Try it: Animate the sieve to 100.

Start with 2 through 30. Since \(\sqrt{30} \approx 5.48\), only \(p = 2, 3, 5\) are needed. Try it: Sieve to 30 by rounds; The primes up to 30.

Survivors: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Ten primes.

To simplify the fraction \(\tfrac{462}{1071}\) you need the largest number dividing both. To tile a \(48 \times 18\) floor with identical square tiles and no cutting, you need the largest square side that divides both lengths. To find the period of two interlocking gears, or to normalise an aspect ratio such as \(1920 \times 1080 \to 16:9\), you need the same thing again: the greatest common divisor.

You could factor both numbers and compare. For \(462 = 2 \cdot 3 \cdot 7 \cdot 11\) and \(1071 = 3^2 \cdot 7 \cdot 17\), the shared part is \(3 \cdot 7 = 21\). But factoring is the hard problem we just met. For 300-digit numbers it is hopeless. Remarkably, there is an algorithm that finds the GCD without factoring anything, and it is about 2,300 years old.

Take the \(48 \times 18\) rectangle. The biggest square you can cut from it is \(18 \times 18\), and you can fit two of them, leaving a \(12 \times 18\) strip. Any square tile that fits the original rectangle exactly also fits the squares (its side divides 18) and therefore fits the leftover strip. Conversely, a tile that fits the \(18 \times 12\) strip fits everything. So the problem has shrunk from \((48, 18)\) to \((18, 12)\) with the same answer. Repeat: one \(12 \times 12\) square leaves \(12 \times 6\). Then two \(6 \times 6\) squares fill it exactly. The answer is 6. Try it: Tile 48 × 18 with squares.

The tiling picture is the following fact, written as algebra.

Proof. Write \(a = qb + r\) with \(r = a \bmod b\). If \(d\) divides \(a\) and \(b\), it divides \(r = a - qb\), because that is an integer combination of \(a\) and \(b\). Conversely, if \(d\) divides \(b\) and \(r\), it divides \(a = qb + r\). So the pairs \((a, b)\) and \((b, r)\) have exactly the same common divisors, and in particular the same greatest one. \(\square\)

Each step replaces the pair with a strictly smaller remainder, and remainders can’t go below 0, so the process must stop. It stops when the remainder is 0, and then \(\gcd(g, 0) = g\).

Every division is written out in full: Try it: gcd(1071, 462) as a trace; gcd and Bézout for 1071, 462.

The last nonzero remainder is 21, so \(\gcd(1071, 462) = 21\). It took three divisions, and nothing was factored. Check: \(1071 = 21 \cdot 51\) and \(462 = 21 \cdot 22\), and \(\gcd(51, 22) = 1\). So

As a trace table, which is how you’d debug it:

Notice that gcd(462, 1071) works too. The first step computes \(462 \bmod 1071 = 462\) and simply swaps the pair. In real code, use math.gcd.

Every two steps, the remainder at least halves. (If \(b \le a/2\), then \(r < b \le a/2\). If \(b > a/2\), then \(q = 1\) and \(r = a - b < a/2\).) So the number of steps is at most about \(2 \log_2 b\): around 2,000 divisions for 1,000-bit numbers, which takes microseconds. Compare that with the astronomically slow factoring approach.

Try it: Lamé’s worst case, 89 and 55.

Comparing factorizations shows what’s going on. GCD takes the minimum exponent of each prime and LCM takes the maximum. Since \(\min(x, y) + \max(x, y) = x + y\), multiplying the two gives back \(ab\):

Worked example. For \(a = 252 = 2^2 \cdot 3^2 \cdot 7\) and \(b = 198 = 2 \cdot 3^2 \cdot 11\): Try it: gcd and lcm of 252, 198; gcd and lcm of 252, 198.

The factorizations agree: the GCD is \(2^1 \cdot 3^2 = 18\) and the LCM is \(2^2 \cdot 3^2 \cdot 7 \cdot 11 = 2772\).

Applications: two cron jobs running every 6 and every 10 minutes coincide every \(\operatorname{lcm}(6, 10) = 30\) minutes. Gears with 12 and 18 teeth return to their starting alignment after \(\operatorname{lcm}(12,18) = 36\) tooth-passes. Planetary conjunctions and traffic-light cycles work the same way.

Here is a puzzle with a long history. You have a 1,071 ml jug and a 462 ml jug and unlimited water. Can you measure exactly 21 ml? Measuring means pouring whole jugfuls in and out of a tank, so the amounts you can reach are \(1071x + 462y\) for integers \(x, y\), where negative means "poured out". The real question is which numbers can be written as \(1071x + 462y\), and with which \(x\) and \(y\).

This isn’t just a puzzle. Finding such \(x, y\) is the way to compute modular inverses (Section 23.8), and modular inverses are how RSA keys get made.

Every number of the form \(1071x + 462y\) is a multiple of 21, because 21 divides both terms. So you can’t measure 10 ml or 20 ml. The surprise is the converse: 21 itself is reachable, so every multiple of 21 is too. The Euclidean algorithm’s divisions, read backwards, tell you exactly how.

Take the divisions from the \(\gcd(1071, 462)\) example and solve each one for its remainder: Try it: Back-substitution, line by line; Check the Bézout coefficients.

Now start from the last line, which already expresses the GCD, and substitute the line above for 147:

So \(x = -3\) and \(y = 7\). Check: \(7 \cdot 462 = 3234\), \(3 \cdot 1071 = 3213\), and \(3234 - 3213 = 21\). With the jugs: fill the small jug 7 times into the tank and empty out the large jug’s worth 3 times.

Back-substitution means storing every line. Code usually keeps a running pair instead. It tracks how each remainder is written in terms of the original \(a\) and \(b\), and updates that alongside the remainders. Each row satisfies \(r_i = a x_i + b y_i\). Try it: The forward extended-Euclid table.

Each new row equals (the row two above) minus \(q\) times (the row above), with \(q\) being the quotient of the two remainders above it. The row just before the 0 gives the GCD and its coefficients.

We promised a proof of unique factorization. Here is the missing piece.

Proof. Suppose \(p \nmid a\). The only positive divisors of \(p\) are 1 and \(p\), so \(\gcd(p, a) = 1\). By Bézout, \(px + ay = 1\) for some integers \(x, y\). Multiply through by \(b\):

\(p\) divides \(pbx\) obviously, and \(p\) divides \(aby\) because \(p \mid ab\). So \(p\) divides their sum, which is \(b\). \(\square\)

The lemma needs \(p\) prime: \(6 \mid 4 \cdot 9\) but \(6 \nmid 4\) and \(6 \nmid 9\). That one fact is why primes behave like atoms.

It is 9 o’clock. What time will it be in 5 hours? Nobody says "14 o’clock" on a 12-hour clock. You say 2. In 100 hours? You don’t count 100 ticks. You throw away whole 12-hour laps. A 32-bit counter at \(2^{32} - 1\) that gets incremented becomes 0. The day of the week, the angle of a rotating wheel, the slot in a ring buffer: these are all quantities where only the remainder matters.

Modular arithmetic is the algebra of "only the remainder matters". The surprise is how much ordinary algebra still works there, and the one rule that doesn’t.

Wrap the number line around a circle of circumference 12. Then 2, 14, 26 and \(-10\) all land on the same spot. Adding means walking clockwise. Subtracting means walking anticlockwise. Multiplying is repeated addition. Try it: 9 + 5 on a clock.

Congruence is an equivalence relation (reflexive, symmetric and transitive; see Chapter 21). That is the formal reason the "columns" picture is legitimate. Each integer belongs to exactly one column.

Here is the key theorem. Suppose \(a \equiv a'\) and \(b \equiv b' \pmod m\). Then

Why. Write \(a' = a + km\) and \(b' = b + lm\). Then

In practice this means you may reduce at any point. Replace any number by its remainder whenever you like, and the final remainder comes out the same. That is what makes huge computations tractable: intermediate values never need to grow past \(m^2\).

Worked example. What is the last digit of \(7 \cdot 13 \cdot 29 \cdot 48\)? "Last digit" means "mod 10".

The last digit is 2. You never needed the full product, which is 126,672.

Since \(10 \equiv 1 \pmod 9\), every power \(10^k \equiv 1^k = 1 \pmod 9\). A number with digits \(d_k \ldots d_1 d_0\) is \(\sum d_i 10^i\). (Here \(\sum\) means "add up the following terms over all values of \(i\)".) So

A number and its digit sum leave the same remainder mod 9, and therefore also mod 3. Similarly, \(10 \equiv -1 \pmod{11}\), so \(10^k \equiv (-1)^k\) and the alternating digit sum gives the remainder mod 11. Old-school "casting out nines" to check hand multiplication is the same idea.

In ordinary arithmetic, \(2x = 2y\) lets you cancel the 2. Mod 6, though, Try it: Zero divisors mod 6.

You can’t cancel 2, because 2 shares a factor with 6. Worse, \(2 \cdot 3 = 6 \equiv 0 \pmod 6\): two nonzero numbers multiply to zero. These are called zero divisors. Division mod \(m\) works only for numbers coprime to \(m\), and modular inverses (Section 23.8) make that precise.

Time and calendars. A flight leaves at 21:00 and the journey, including a stopover, takes 50 hours. Arrival is at \(21 + 50 = 71 \equiv 23 \pmod{24}\), so 23:00, and \(\lfloor 71/24 \rfloor = 2\) days later. Days of the week work mod 7: since \(365 = 52 \cdot 7 + 1 \equiv 1 \pmod 7\), a date moves one weekday later each ordinary year (two after a leap day). Christmas 2026 is a Friday, so Christmas 2027 is a Saturday.

Navigation and physics. Compass bearings live mod 360: a ship on heading 350° that turns 30° to starboard is on heading \(380 \bmod 360 = 20\)°. Phase angles of waves and alternating currents live mod \(2\pi\) (see Chapter 13), which is why a phase of \(370°\) and one of \(10°\) describe the same signal.

Music. Western pitch classes are residues mod 12: an octave is 12 semitones, a perfect fifth is 7. Stepping up by fifths gives \(0, 7, 14 \equiv 2, 9, 16 \equiv 4, \ldots\); because \(\gcd(7, 12) = 1\) the walk visits all 12 pitch classes before returning to the start. That walk is the circle of fifths. Stepping by 4 semitones (a major third) instead, with \(\gcd(4, 12) = 4\), cycles through only 3 notes.

Ask Python and C the same question: Try it: % on negatives, language by language.

(In Python, integer division is //.) Both camps are internally consistent. They disagree on which quotient to pick.

Every language preserves the identity

so choosing \(q\) determines \(r\). For \(-7 / 2 = -3.5\) there are two natural choices:

Python’s math.fmod and int(a / b) give you the C-style behaviour when you need it. Be careful with int(a / b) for huge integers, though, since it goes through floating point.

Solve \(7x \equiv 3 \pmod{26}\). In ordinary arithmetic you’d divide by 7. Mod 26 there are no fractions, so what does "divide by 7" even mean? We need a whole number that acts like \(\tfrac{1}{7}\): something that, multiplied by 7, gives 1.

The two multiplication tables below show this. Mod 7 (a prime) every nonzero row contains exactly one 1. Mod 8, the rows for 2, 4 and 6, which share a factor with 8, never reach 1 and even hit 0.

Try it: Explore tables mod 7 and 8.

Euclid on \((26, 7)\): Try it: 7⁻¹ mod 26, step by step; Compute 7⁻¹ mod 26.

Back-substitute, starting from the line that produced 1:

Mod 26 the \(3 \cdot 26\) term vanishes, leaving \(-11 \cdot 7 \equiv 1\). So \(7^{-1} \equiv -11 \equiv 15 \pmod{26}\). Check: \(7 \cdot 15 = 105 = 4 \cdot 26 + 1\). Correct.

Now solve \(7x \equiv 3 \pmod{26}\) by multiplying both sides by 15:

Check: \(7 \cdot 19 = 133 = 5 \cdot 26 + 3\). Correct.

(mod_inverse reuses extended_gcd from Section 23.5. Here \(x\) is the coefficient of \(a\), which is the one we want.)

\(ax \equiv b \pmod m\) has solutions exactly when \(g = \gcd(a, m)\) divides \(b\). In that case, divide everything by \(g\) and solve the smaller congruence, which gives \(g\) solutions mod \(m\). Example: \(4x \equiv 6 \pmod{10}\). Here \(g = 2\) divides 6, so dividing by 2 gives \(2x \equiv 3 \pmod 5\). Since \(2^{-1} \equiv 3 \pmod 5\), we get \(x \equiv 9 \equiv 4 \pmod 5\). Mod 10 that means \(x \in \{4, 9\}\). Check: \(16 \equiv 6\) and \(36 \equiv 6 \pmod{10}\). In contrast, \(4x \equiv 5 \pmod{10}\) has no solutions, since \(4x\) is always even and so is \(10\): the difference would be odd. Try it: Solve 4x ≡ 6 (mod 10).

Try it: Solve a CRT system.

Compute the powers of 3 mod 7: \(3, 2, 6, 4, 5, 1, 3, 2, 6, \ldots\) The sequence repeats with period 6. Powers of 2 mod 7 go \(2, 4, 1, 2, 4, 1, \ldots\) with period 3. Both periods divide 6, which is one less than the prime 7. Coincidence?

Take \(p = 7\), \(a = 3\), and multiply each of \(1, 2, 3, 4, 5, 6\) by 3, mod 7:

You get \(3, 6, 2, 5, 1, 4\), which is the same six numbers in a different order. That always happens. If \(ai \equiv aj\), multiplying by \(a^{-1}\) gives \(i \equiv j\), so no two products collide, and none is 0. Now multiply all six products together. They’re the same numbers, so they have the same product:

Replace 7 by \(p\) and 3 by \(a\) and the argument is the general proof.

Fermat lets you reduce an exponent mod \(p - 1\).

Worked example: \(3^{100} \bmod 7\). Since \(3^6 \equiv 1\) and \(100 = 16 \cdot 6 + 4\): Try it: Compute 3¹⁰⁰ mod 7.

Worked example: \(7^{222} \bmod 11\). \(7^{10} \equiv 1\) and \(222 = 22 \cdot 10 + 2\), so \(7^{222} \equiv 7^2 = 49 \equiv 5 \pmod{11}\).

For a composite modulus, replace \(p - 1\) with Euler’s totient \(\varphi(n)\), the count of numbers in \(1 \ldots n\) that are coprime to \(n\). Euler’s theorem: if \(\gcd(a, n) = 1\), then \(a^{\varphi(n)} \equiv 1 \pmod n\). For a prime, \(\varphi(p) = p - 1\). For a product of two distinct primes, \(\varphi(pq) = (p-1)(q-1)\): of the \(pq\) numbers, the \(q\) multiples of \(p\) and the \(p\) multiples of \(q\) are excluded, and \(pq\) itself was counted twice, so \(pq - p - q + 1 = (p-1)(q-1)\). RSA is built on this formula.

Turn the theorem around. If \(a^{n-1} \not\equiv 1 \pmod n\) for some \(a\), then \(n\) is definitely composite, and we learned that without finding a factor. For example, \(2^{14} = 16384 = 1092 \cdot 15 + 4\), so \(2^{14} \equiv 4 \not\equiv 1 \pmod{15}\) and 15 is composite.

RSA needs things like \(m^{65537} \bmod n\) with \(n\) around 600 digits long. Computing \(m^{65537}\) first is absurd: the number would have about 40 million digits before you reduced it. Multiplying by \(m\) 65,536 times, reducing as you go, keeps numbers small but takes too many steps once exponents are themselves 600 digits long. We need something exponentially better.

Squaring doubles the exponent: \(a \to a^2 \to a^4 \to a^8 \to \cdots\). After 10 squarings you have \(a^{1024}\). Any exponent is a sum of powers of 2, its binary expansion, so multiply together the squarings you need:

An \(n\)-bit exponent needs at most \(n\) squarings and \(n\) multiplications. For a 2048-bit exponent that is about 4,000 operations instead of \(2^{2048}\). Reducing mod \(m\) after each step (allowed by Section 23.6) keeps every number below \(m^2\).

First tabulate the repeated squares of 7 mod 11: Try it: 7¹³ mod 11, bit by bit; Compute 7¹³ mod 11.

Since \(13 = 8 + 4 + 1\), multiply the matching rows and reduce at each step:

The procedure does the same thing bit by bit (\(13 = 1101_2\), read from the right):

Cross-check with Fermat: \(7^{10} \equiv 1\), so \(7^{13} \equiv 7^3 = 343 = 31 \cdot 11 + 2 \equiv 2\). Correct.

A hash table with \(m\) buckets stores key \(k\) in bucket \(h(k) \bmod m\), where \(h\) scrambles the key into a big integer. The remainder lands in \(0 \ldots m-1\) (if you use floor-mod!) and spreads keys around, provided the keys don’t share structure with \(m\).

Keys that are all multiples of 8 collide completely in 8 buckets, but spread out across 7. In general, the keys \(k, k + s, k + 2s, \ldots\) hit only \(m / \gcd(s, m)\) distinct buckets. A prime \(m\) shares no factor with any stride smaller than itself. That is the classical case for prime table sizes. Modern tables (Python’s dict, Java’s HashMap, Rust’s HashMap) use power-of-two sizes for speed (& (m - 1) instead of division) and compensate by mixing the hash bits thoroughly first. Java’s HashMap XORs the high half of the hash into the low half before masking.

Hash functions themselves are modular arithmetic. Java’s String.hashCode is

computed by Horner’s rule (\(h \leftarrow 31h + s_i\)), with the mod coming free from 32-bit overflow. For "hi" it gives \(104 \cdot 31 + 105 = 3329\). The Rabin–Karp substring search uses the same polynomial hash mod a large prime. Sliding the window by one character updates the hash in constant time: subtract the old leading character’s term, multiply by the base, add the new character.

A check digit is one extra digit chosen so that some modular sum comes out to 0. Typing errors break the sum.

ISBN-10 uses weights 10 down to 1 and requires

where a check value of 10 is written X. Worked example: 0-306-40615-2. Try it: Check the ISBN-10 example.

Why 11 and not 10? Because 11 is prime. A single wrong digit changes the sum by \(w \cdot (\text{error})\), where both factors are nonzero and less than 11, so by Euclid’s lemma 11 can’t divide the change. Swapping adjacent digits \(x, y\) changes the sum by \(\pm(x - y)\), again not a multiple of 11 unless \(x = y\). So every single-digit error and every adjacent swap is caught. (ISBN-13 switched to weights 1, 3, 1, 3, …​ mod 10, which misses a few swaps, for compatibility with retail barcodes.)

The Luhn algorithm protects credit-card and IMEI numbers. From the right, double every second digit, and if a doubled value exceeds 9, subtract 9 (which is the same as adding its two digits). The total must be \(\equiv 0 \pmod{10}\).

Worked example: 7992 7398 713. Reading from the right, the digits are 3, 1, 7, 8, 9, 3, 7, 2, 9, 9, 7. The odd positions (1, 8, 3, 2, 9) are doubled to 2, 16, 6, 4, 18, which become 2, 7, 6, 4, 9 after subtracting 9 where needed. Even positions (3, 7, 9, 7, 9, 7) stay as they are. Try it: Check the Luhn example.

A computer is deterministic, yet simulations, games and randomised algorithms need numbers that look random. The oldest workable trick is the linear congruential generator (LCG):

Pick a seed \(x_0\) and iterate. There are only \(m\) possible states, so the sequence must eventually cycle. A well-chosen LCG cycles through all \(m\) values before repeating.

Worked example: \(a = 5\), \(c = 3\), \(m = 16\), seed \(x_0 = 7\). Try it: Trace the LCG’s 16 states.

All 16 values appear before 7 recurs and the cycle restarts at 6. This is no accident. The Hull–Dobell theorem says an LCG has full period \(m\) exactly when \(\gcd(c, m) = 1\), \(a - 1\) is divisible by every prime factor of \(m\), and \(a - 1\) is divisible by 4 if \(m\) is. Here \(c = 3\) is coprime to 16 and \(a - 1 = 4\) is divisible by both 2 and 4.

You want to send your card number to a shop you’ve never contacted, over a network where anyone can read every byte. Classical ciphers need a shared secret key. How do you agree on one when every message is public? Before 1976 almost everyone assumed this was impossible. Number theory says otherwise.

The idea needs only modular powers and one observation: \((g^a)^b = g^{ab} = (g^b)^a\).

Worked example with \(p = 23\), \(g = 5\), Alice’s \(a = 6\), Bob’s \(b = 15\). The repeated squares of 5 mod 23 are Try it: Diffie–Hellman with an eavesdropper; Compute 5⁶ mod 23.

Both arrive at the shared secret 2. An eavesdropper sees \(p = 23\), \(g = 5\), \(A = 8\) and \(B = 19\). To get the secret they must recover \(a\) from \(5^a \equiv 8\). That is the discrete logarithm problem. It’s trivial for \(p = 23\) (try all 22 exponents) but believed infeasible when \(p\) has 600+ digits, even though computing \(g^a\) is fast. Modern TLS usually does the same dance on an elliptic curve instead of with integers mod \(p\).

Diffie–Hellman agrees on a key. RSA (Rivest, Shamir, Adleman, 1977) goes further: a public key that anyone can use to encrypt a message to you, and a private key that only you can use to decrypt. It rests on everything in this chapter:

Step 1: primes. \(p = 5\) and \(q = 11\). Then Try it: Tiny RSA, every step; Find d = 3⁻¹ mod 40.

Step 2: public exponent. Try \(e = 3\). Since \(40 = 13 \cdot 3 + 1\), we have \(\gcd(40, 3) = \gcd(3, 1) = 1\), so \(e = 3\) is allowed.

Step 3: private exponent. We need \(3d \equiv 1 \pmod{40}\). The Euclid line \(40 = 13 \cdot 3 + 1\) rearranges to

Check: \(3 \cdot 27 = 81 = 2 \cdot 40 + 1\). Correct. The public key is \((n, e) = (55, 3)\) and the private key is \(d = 27\).

Step 4: encrypt the message \(M = 7\):

Step 5: decrypt \(C = 13\) by computing \(13^{27} \bmod 55\) with square-and-multiply. In binary \(27 = 11011_2 = 16 + 8 + 2 + 1\). The squares are Try it: Decrypt 13²⁷ mod 55.

and multiplying the ones we need gives

The receiver recovers \(M = 7\).

Because \(ed \equiv 1 \pmod{\varphi}\), we have \(ed = 1 + k\varphi\) for some integer \(k\). In the example, \(3 \cdot 27 = 81 = 1 + 2 \cdot 40\). If \(\gcd(M, n) = 1\), Euler’s theorem gives

(If \(M\) happens to share a factor with \(n\), the result still holds. Applying Fermat separately mod \(p\) and mod \(q\) and combining with the Chinese remainder theorem shows it.)

Why it’s secure. An attacker knows \(n\) and \(e\). To find \(d\) they need \(\varphi = (p-1)(q-1)\), and getting that from \(n\) is as hard as factoring \(n\). With \(n = 55\), factoring takes a second. Real keys use primes of 1,024+ bits each, giving a 617-digit \(n\), and the best known algorithms would take far longer than the age of the universe.

The same arithmetic at the size of a classic textbook example: Try it: RSA with 61 and 53.