4. Number Theory

Number theory studies the integers, and especially divisibility: which numbers divide which, how every integer breaks into primes, and what happens when arithmetic wraps around a fixed modulus. These questions were once purely theoretical. Today they underlie hashing, checksums, pseudorandom generators, and public-key cryptography. This chapter goes from the division algorithm to RSA, and pairs each theorem with the algorithm that computes it.

<a id="41-divisibility"></a>

4.1 Divisibility

This subchapter defines divisibility and introduces primes as the multiplicative building blocks of the integers. It then proves that every integer factors into primes in exactly one way and that the supply of primes never runs out.

Divisibility and the Division Algorithm

Why. Many everyday computing questions ask what is left over when one integer is divided by another. Does this batch size split the dataset evenly? Which bucket does key k go into? What day of the week is day 1000? The integers are not closed under division, so we need precise language for when division is exact and for what remains when it is not.

What. Let a and b be integers with a ≠ 0. We say a divides b, written a ∣ b, if there is an integer k with b = a·k. Then a is a divisor (or factor) of b, and b is a multiple of a. We write a ∤ b when a does not divide b.

Examples: 3 ∣ 12, 3 ∤ 13, −4 ∣ 12, 1 ∣ b for every b, and a ∣ 0 for every a ≠ 0.

Property	Statement	Reason
Linear combinations	a ∣ b and a ∣ c ⇒ a ∣ (bx + cy) for all integers x, y	b = ak, c = al ⇒ bx + cy = a(kx + ly)
Multiples	a ∣ b ⇒ a ∣ bc for every integer c	bc = a(kc)
Transitivity	a ∣ b and b ∣ c ⇒ a ∣ c	c = bl = a(kl)
Size	a ∣ b and b ≠ 0 ⇒ |a| ≤ |b|	|b| = |a|·|k| with |k| ≥ 1
Antisymmetry on ℤ⁺	a ∣ b and b ∣ a ⇒ a = b	Follows from the size property

The first property is used constantly in this chapter. It says that divisibility survives any integer linear combination. Reflexivity, antisymmetry, and transitivity make (ℤ⁺, ∣) a partial order (2.5).

The division algorithm. For every integer a and every positive integer d, there are unique integers q and r with a = d·q + r and 0 ≤ r < d. The quotient is q = a div d = ⌊a/d⌋ and the remainder is r = a mod d (floor function, 2.2). In particular, d ∣ a if and only if a mod d = 0. Despite the name, this is a theorem, not a procedure.

Proof. Existence: the set S = {a − dq : q ∈ ℤ and a − dq ≥ 0} is non-empty, because q = −|a| gives a + d·|a| ≥ a + |a| ≥ 0. By the well-ordering principle (3.2), S has a least element r = a − dq, and r ≥ 0. If r ≥ d, then r − d = a − d(q + 1) would be a smaller element of S, a contradiction. So 0 ≤ r < d. Uniqueness: if dq + r = dq' + r' with 0 ≤ r, r' < d, then d(q − q') = r' − r. The right side lies strictly between −d and d, and the only multiple of d in that range is 0. So r = r' and q = q'. ∎

Analogy. Deal a cards to d players. Everyone receives q cards and r cards are left over. There are always fewer than d left, because otherwise you would deal another full round.

  a = 17, d = 5:   17 = 5·3 + 2

  0         5         10        15   17   20
  |---------|---------|---------|----x----|
  └──── q = 3 full steps of d ──┘└r┘
                                  r = 2

Negative numbers and programming languages. The theorem requires 0 ≤ r < d, so −11 = 3·(−4) + 1, which gives −11 div 3 = −4 and −11 mod 3 = 1. Programming languages do not all agree with this:

Language	−11 divided by 3	−11 % 3	Rule
Mathematics (this chapter)	−4	1	Remainder always in [0, d)
Python	-11 // 3 == -4	1	Floor division: the remainder takes the sign of the divisor
Java, C, C++, Go	-11 / 3 == -3	-2	Truncation toward zero: the remainder takes the sign of the dividend
JavaScript	Math.trunc(-11 / 3) === -3	-2	Same as Java for %

def division(a, d):
    """Return (q, r) with a == d*q + r and 0 <= r < d, for d > 0."""
    q, r = divmod(a, d)                  # Python's divmod uses floor division, matching the theorem
    assert a == d * q + r and 0 <= r < d
    return q, r

print(division(17, 5))                   # (3, 2)    17 = 5·3 + 2
print(division(-11, 3))                  # (-4, 1)   -11 = 3·(-4) + 1
print(division(12, 4))                   # (3, 0)    remainder 0, so 4 | 12

def divides(a, b):
    return b % a == 0                    # a | b  iff  b mod a == 0   (a != 0)

print([d for d in range(1, 31) if divides(d, 30)])   # [1, 2, 3, 5, 6, 10, 15, 30]

int a = -11, d = 3;
System.out.println(a / d);                  // -3   truncates toward zero
System.out.println(a % d);                  // -2   sign follows the dividend
System.out.println(Math.floorDiv(a, d));    // -4   matches the division algorithm
System.out.println(Math.floorMod(a, d));    // 1    always in [0, d) when d > 0

Key takeaways

• a ∣ b means b = ak for some integer k. Divisibility is preserved by integer linear combinations.
• Division algorithm: for d > 0 there are unique q, r with a = dq + r and 0 ≤ r < d, namely q = ⌊a/d⌋ and r = a mod d.
• d ∣ a if and only if a mod d = 0.
• For negative operands, Python's % follows the theorem, but C-family % can return a negative value. Use Math.floorMod or ((a % d) + d) % d when you need a remainder in [0, d).

Practice

1. (Beginner) Find q and r for (a, d) = (101, 11), (−101, 11), and (0, 7). Check that 0 ≤ r < d in each case.
2. (Intermediate) Prove that if a ∣ b and b ∣ c, then a ∣ c. Then prove or disprove: if a ∣ bc, then a ∣ b or a ∣ c.
3. (Interview) A circular buffer of size n steps back k slots with index = (head - k) % n. Why is this correct in Python but can produce a negative index in Java or C? Fix it without adding a branch. Hint: add a multiple of n before taking the remainder, or use Math.floorMod.

Primes

Why. Under multiplication, primes are the atoms: they cannot be split further, and every other integer is built from them. Many algorithms need primes or need to know whether a number is prime. Examples include hash table sizes, cryptographic keys, and randomized fingerprints.

What. 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, which means n = a·b with 1 < a, b < n. The number 1 is neither prime nor composite. Excluding it keeps the factorization in the next topic unique, because otherwise 6 = 2·3 = 1·2·3 would count as two factorizations.

The primes below 50 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. The number 2 is the only even prime.

How: the √n bound. If n is composite, then n has a prime divisor p ≤ √n.

Proof. Write n = ab with 1 < a ≤ b. Then a² ≤ ab = n, so a ≤ √n. The integer a ≥ 2 has a prime divisor (3.2), which is at most a ≤ √n and also divides n. ∎

So to test n for primality, it is enough to try divisors up to √n. Divisors come in pairs (a, n/a), and the smaller member of each pair is at most √n:

  divisor pairs of 36:
     1 · 36
     2 · 18
     3 · 12
     4 · 9
     6 · 6       <- √36 = 6: every pair has a member ≤ 6

def is_prime(n):
    """Trial division up to √n: O(√n) divisions."""
    if n < 2:
        return False                     # 0, 1 and negative numbers are not prime
    if n % 2 == 0:
        return n == 2                    # 2 is the only even prime
    d = 3
    while d * d <= n:                    # test d² ≤ n in integers, so no floating-point sqrt is needed
        if n % d == 0:
            return False                 # found a divisor ≤ √n, so n is composite
        d += 2                           # only odd candidates remain
    return True

print([n for n in range(50) if is_prime(n)])
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
print(is_prime(1_000_003), is_prime(1_000_001))   # True False   (1000001 = 101 · 9901)

How many primes are there? Let π(n) be the number of primes ≤ n. The Prime Number Theorem states that π(n) ≈ n / ln n for large n. Equivalently, a random integer near n is prime with probability about 1 / ln n.

n	π(n)	n / ln n
10	4	4.3
100	25	21.7
1 000	168	144.8
1 000 000	78 498	72 382

Primes thin out, but slowly. A random 1024-bit number is prime with probability about 1/710, because ln 2¹⁰²⁴ ≈ 710. That is why cryptographic libraries generate large primes by picking random odd numbers and testing them until one passes.

Cost. Trial division takes O(√n) steps, which looks small but is exponential in the number of digits. A b-bit number needs about 2^{b/2} divisions. For numbers with hundreds of digits, practical code uses probabilistic tests such as Miller–Rabin, which builds on Fermat's little theorem (4.4).

Key takeaways

• A prime is an integer greater than 1 whose only positive divisors are 1 and itself. 1 is not prime.
• A composite n has a prime factor ≤ √n, so trial division can stop at √n.
• Trial division costs O(√n), which is exponential in the bit length. Large numbers need probabilistic tests.
• π(n) ≈ n / ln n: primes thin out slowly, so random search finds large primes quickly.

Practice

1. (Beginner) Use the √n bound to decide whether 221 and 223 are prime. Which trial divisors do you need in each case?
2. (Intermediate) Prove that every prime p > 3 has the form 6k + 1 or 6k + 5. Use this to reduce the candidate divisors in is_prime to one third of all integers. Hint: use proof by cases on n mod 6 (1.4).
3. (Interview) A key generator needs a random 2048-bit prime. About how many random candidates must it test on average, and how can it make each rejection cheaper? Hint: use π(n) ≈ n / ln n to estimate the density of primes near 2²⁰⁴⁸. Then consider skipping even numbers and dividing by a short list of small primes before running an expensive test.

Fundamental Theorem of Arithmetic

Why. Writing 360 = 2³·3²·5 is useful only if it is the factorization of 360. If an integer could factor into primes in two different ways, many tools would break: the gcd formula below, the injective encoding (a, b) ↦ 2ᵃ·3ᵇ from 2.3, and much of cryptography. The Fundamental Theorem of Arithmetic guarantees that the factorization is unique.

What. Every integer n ≥ 2 can be written as a product of primes, and this product is unique up to the order of the factors. Grouping equal primes gives the canonical form

n = p₁^e₁ · p₂^e₂ · ⋯ · pₘ^eₘ      with primes p₁ < p₂ < ⋯ < pₘ and exponents eᵢ ≥ 1

Existence was proved by strong induction in 3.2: a prime is its own factorization, and a composite n = ab combines the factorizations of a and b.

Uniqueness needs Euclid's lemma: if a prime p divides ab, then p ∣ a or p ∣ b. Its proof uses Bézout's identity and is given in 4.2. The lemma fails for composites: 6 ∣ 4·9 = 36, but 6 ∤ 4 and 6 ∤ 9. By induction, the lemma extends to products of many factors.

Proof of uniqueness. Suppose some integer has two different prime factorizations, and let n be the smallest such integer (well-ordering, 3.2): n = p₁p₂⋯pₖ = q₁q₂⋯qₗ. Since p₁ divides q₁q₂⋯qₗ, Euclid's lemma gives p₁ ∣ qⱼ for some j, and because qⱼ is prime, p₁ = qⱼ. Removing this common factor from both sides gives two different factorizations of n / p₁ < n, which contradicts the minimality of n. ∎

                360
               /   \
             36     10
            /  \   /  \
           6    6 2    5
          / \  / \
         2   3 2  3

  Any order of splitting gives the same leaves {2, 2, 2, 3, 3, 5}, so 360 = 2³ · 3² · 5

How: reading facts off the exponents. Write n = ∏ p^{e_p}, where e_p is the exponent of the prime p in n (0 if p does not divide n). The factorization is then a multiset of primes (2.1), and many questions reduce to comparing exponents:

Question	Answer from the factorization
Does d divide n?	Yes if and only if f_p ≤ e_p for every prime p, where d = ∏ p^{f_p}
How many positive divisors does n have?	τ(n) = ∏ (e_p + 1): each exponent is chosen independently from 0, …, e_p
gcd(a, b) and lcm(a, b)	Minimum and maximum of the exponents (4.2)
Is n a perfect square?	Yes if and only if every e_p is even

For 360 = 2³·3²·5, the number of divisors is τ(360) = 4·3·2 = 24.

from collections import Counter
from math import prod

def factorize(n):
    """Prime factorization of n >= 2 as {prime: exponent}, by trial division."""
    f = Counter()
    d = 2
    while d * d <= n:
        while n % d == 0:          # divide d out completely before moving on, so every d
            f[d] += 1              # that still divides n here must be prime
            n //= d
        d += 1
    if n > 1:
        f[n] += 1                  # the remaining n > 1 has no factor ≤ its square root, so it is prime
    return dict(f)

def num_divisors(n):
    return prod(e + 1 for e in factorize(n).values())   # choose each exponent from 0..e

print(factorize(360))              # {2: 3, 3: 2, 5: 1}
print(factorize(97))               # {97: 1}
print(num_divisors(360))           # 24
print(factorize(2**32 + 1))        # {641: 1, 6700417: 1}   Euler disproved Fermat's guess that this is prime

Multiplying primes is easy, but recovering the primes from a large product is believed to be hard. No known classical algorithm factors a 600-digit number in reasonable time. RSA (4.4) is built on this asymmetry.

Key takeaways

• Every integer n ≥ 2 is a product of primes in exactly one way, up to the order of the factors.
• Existence follows from strong induction. Uniqueness rests on Euclid's lemma: p ∣ ab ⇒ p ∣ a or p ∣ b.
• The exponents answer divisibility questions: d ∣ n exactly when every exponent of d is at most the matching exponent of n, and τ(n) = ∏ (e_p + 1).
• Multiplying is easy and factoring is believed to be hard. Public-key cryptography depends on this asymmetry.

Practice

1. (Beginner) Factor 1001, 1024, and 2025, and give the number of positive divisors of each.
2. (Intermediate) Prove that √2 is irrational using the Fundamental Theorem of Arithmetic. Hint: if √2 = a/b, then 2b² = a². Compare the exponent of 2 on both sides. Then generalize the argument to √n for any n that is not a perfect square.
3. (Interview) How many trailing zeros does 100! have? Compute it without evaluating 100!. Hint: each trailing zero needs one factor 2 and one factor 5, and factors of 2 are more plentiful. Count the exponent of 5 in 100! by adding ⌊100/5⌋ and ⌊100/25⌋.

Sieve of Eratosthenes

Why. Trial division tests one number at a time. When you need all primes up to N, for example to precompute a table, factor many numbers, or count primes, testing each number separately costs about N·√N operations. The sieve handles the whole range in nearly linear time by crossing out multiples instead of searching for divisors.

What. List the integers 2, 3, …, N. Repeatedly take the smallest number p that is not crossed out. It is prime, because no smaller prime divides it. Cross out its multiples, starting at p²: any smaller multiple k·p with k < p has a prime factor smaller than p and was crossed out earlier. Stop when p² > N. Every number that is still not crossed out is prime.

  N = 30. Each composite shows the prime that crossed it out first. 1 is marked -.

    -    2    3  [2]    5  [2]    7  [2]  [3]  [2]
   11  [2]   13  [2]  [3]  [2]   17  [2]   19  [2]
  [3]  [2]   23  [2]  [5]  [2]  [3]  [2]   29  [2]

  Next candidate p = 7: 7² = 49 > 30, so stop.   Primes ≤ 30: 2 3 5 7 11 13 17 19 23 29

Cost. The prime p crosses out about N/p numbers, and the sum of N/p over the primes p ≤ √N is about N·ln ln N. The sieve therefore runs in O(N log log N) time and uses O(N) memory. In practice the running time is nearly linear, and memory is the real limit.

from math import isqrt

def sieve(n):
    """Return all primes <= n. O(n log log n) time, O(n) space."""
    if n < 2:
        return []
    is_p = [True] * (n + 1)
    is_p[0] = is_p[1] = False                      # 0 and 1 are not prime
    for p in range(2, isqrt(n) + 1):               # a prime p > √n has no multiples left to cross out
        if is_p[p]:
            for m in range(p * p, n + 1, p):       # smaller multiples k·p (k < p) are already crossed out
                is_p[m] = False
    return [i for i, flag in enumerate(is_p) if flag]

print(sieve(30))                     # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
print(len(sieve(1_000_000)))         # 78498

Variant: smallest prime factor. Instead of a true/false flag, store for each m the first prime that reaches it. Factoring any m ≤ N then takes O(log m) steps: repeatedly divide by spf[m].

from math import isqrt

def smallest_prime_factors(n):
    spf = list(range(n + 1))                       # spf[m] = m until a smaller prime factor is found
    for p in range(2, isqrt(n) + 1):
        if spf[p] == p:                            # p was never reached by a smaller prime, so it is prime
            for m in range(p * p, n + 1, p):
                if spf[m] == m:
                    spf[m] = p                     # the first prime to reach m is its smallest factor
    return spf

spf = smallest_prime_factors(100)
m, factors = 84, []
while m > 1:
    factors.append(spf[m])                         # peel off the smallest prime factor
    m //= spf[m]
print(factors)                                     # [2, 2, 3, 7]

Method	Task	Time	Space
Trial division	Is n prime?	O(√n)	O(1)
Sieve of Eratosthenes	All primes ≤ N	O(N log log N)	O(N)
Segmented sieve	All primes in [L, R]	O((R − L) log log R + √R)	O(√R + (R − L))
Miller–Rabin (4.4)	Is n prime? (probabilistic)	O(k log³ n) for k rounds	O(1)

Key takeaways

• The sieve crosses out the multiples of each prime p, starting from p², and stops once p > √N.
• It finds all primes ≤ N in O(N log log N) time, compared with O(√n) per number for trial division.
• Memory (O(N)) is the practical limit. A segmented sieve processes the range in blocks.
• Storing the smallest prime factor turns the sieve into a fast factorization table.

Practice

1. (Beginner) Run the sieve by hand for N = 50. Which primes do you sieve with, and why can you stop after them?
2. (Intermediate) Explain why the inner loop may start at p² instead of 2p, and why the outer loop may stop at √N. Then modify sieve to store only odd numbers, which halves its memory.
3. (Interview) You must answer 10⁶ queries of the form "how many primes lie in [L, R]?" with R ≤ 10⁷. Design a solution. Hint: sieve once, then build a prefix-sum array over the prime flags (3.1). Each query then becomes a single subtraction.

Infinitude of Primes

Why. Primes thin out as numbers grow. Could they run out completely? If they did, every integer would be built from a fixed finite list of primes, and key generation would eventually have nothing left to choose from. Euclid's proof (about 300 BC) shows that this never happens. It is also a model proof by contradiction that contains an algorithm.

What. There are infinitely many primes.

Proof (Euclid). Suppose there are only finitely many primes p₁, p₂, …, pₖ. Let N = p₁p₂⋯pₖ + 1. Since N ≥ 2, it has a prime divisor q. Because q must be one of the pᵢ, it divides the product p₁⋯pₖ. Then q divides N − p₁⋯pₖ = 1, which is impossible. ∎

A common misreading. The proof does not claim that N is prime. It claims only that N has a prime factor missing from the list:

Primes in the list	N = product + 1	Factorization of N
2	3	prime
2, 3	7	prime
2, 3, 5	31	prime
2, 3, 5, 7	211	prime
2, 3, 5, 7, 11	2311	prime
2, 3, 5, 7, 11, 13	30031	59 · 509, so two new primes, but N is not prime

How: the proof as an algorithm. The argument is constructive (1.4). Starting from any finite list of primes, it produces a prime outside the list. Repeating it generates new primes forever, although the numbers grow very quickly. Always taking the smallest new prime factor gives the Euclid–Mullin sequence:

from math import factorial, prod

def smallest_factor(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return d
        d += 1
    return n                                       # no factor ≤ √n, so n is prime

primes = [2]
for _ in range(7):
    N = prod(primes) + 1                           # Euclid's number for the current list
    primes.append(smallest_factor(N))              # its prime factors are all outside the list
print(primes)                                      # [2, 3, 7, 43, 13, 53, 5, 6221671]

# Primes never run out, yet the gaps between them grow arbitrarily long:
# n! + k is divisible by k for 2 <= k <= n, so these n - 1 consecutive numbers are all composite.
n = 6
print([factorial(n) + k for k in range(2, n + 1)])   # [722, 723, 724, 725, 726]

Related results, stated without proof:

Result	Statement
Dirichlet's theorem	If gcd(a, m) = 1, there are infinitely many primes ≡ a (mod m) (congruences, 4.3)
Prime gaps	For every n, there is a run of n − 1 consecutive composites (shown in the code above)
Twin prime conjecture (open)	There are infinitely many primes p such that p + 2 is also prime

Key takeaways

• There are infinitely many primes. For any finite list of primes, their product plus 1 has a prime factor that is not on the list.
• p₁⋯pₖ + 1 need not be prime itself. The proof only guarantees a new prime factor.
• The proof is constructive: it is an algorithm that produces new primes, though slowly.
• Primes never run out, yet gaps between consecutive primes can be arbitrarily long.

Practice

1. (Beginner) Compute 2·3·5·7·11·13 + 1 and confirm that it is composite. Explain why this does not contradict Euclid's proof.
2. (Intermediate) Prove that there are infinitely many primes of the form 4k + 3. Hint: suppose p₁, …, pₖ are all of them and consider N = 4p₁⋯pₖ − 1. A product of numbers that are each ≡ 1 (mod 4) is itself ≡ 1 (mod 4).
3. (Interview) Write a generator that yields primes forever, with no fixed upper bound. Hint: either rerun a sieve with a doubled bound whenever you run out, or keep a dictionary that maps each upcoming composite to the primes that will cross it out (an incremental sieve).

<a id="42-gcd-and-lcm"></a>

4.2 GCD and LCM

The greatest common divisor and the least common multiple measure what two integers have in common. This subchapter defines both and presents Euclid's algorithm, one of the oldest algorithms still in daily use. It then extends the algorithm to produce the Bézout coefficients that modular inverses (4.3) and RSA (4.4) depend on.

Greatest Common Divisor

Why. Reducing the fraction 84/120 to 7/10, tiling an 84 × 120 floor with the largest possible square tiles, and checking whether two gear wheels ever realign all ask for the same thing: the largest number that divides both values.

What. For integers a and b that are not both zero, the greatest common divisor gcd(a, b) is the largest integer d with d ∣ a and d ∣ b. By convention, gcd(0, 0) = 0. Two integers are relatively prime (or coprime) if gcd(a, b) = 1. A list a₁, …, aₙ is pairwise relatively prime if every pair in it is coprime.

Property	Statement
Symmetry	gcd(a, b) = gcd(b, a)
Signs do not matter	gcd(a, b) = gcd(−a, b) = gcd(a, −b)
Zero	gcd(a, 0) = a for a > 0
Euclid step	gcd(a, b) = gcd(b, a mod b) (Euclidean algorithm, below)
Scaling	gcd(ka, kb) = k · gcd(a, b) for k > 0
Greatest in the divisibility sense	Every common divisor of a and b divides gcd(a, b) (Bézout's identity, below)

The last property says that the gcd is greatest not only in size but also under divisibility. This makes it the meet of a and b in the lattice (ℤ⁺, ∣) (2.5).

How: via prime factorizations. By the Fundamental Theorem of Arithmetic (4.1), d ∣ a exactly when every prime exponent of d is at most that of a. The gcd therefore takes the minimum exponent of each prime. As a multiset of prime factors, it is the intersection of the two multisets (2.1).

                 2    3    5    7
     84   =     2² · 3¹ · 5⁰ · 7¹
    120   =     2³ · 3¹ · 5¹ · 7⁰
    gcd   =     2² · 3¹ · 5⁰ · 7⁰   =  12     (minimum of each column)

    84/120 = (12·7)/(12·10) = 7/10

This method is correct but impractical for large numbers, because it needs their factorizations. The Euclidean algorithm below computes the gcd without factoring anything.

from fractions import Fraction
from math import gcd

def gcd_naive(a, b):
    """Largest d dividing both a and b, by trying every candidate: O(min(|a|, |b|))."""
    a, b = abs(a), abs(b)
    if a == 0 or b == 0:
        return a + b                                # gcd(x, 0) = |x|
    return max(d for d in range(1, min(a, b) + 1) if a % d == 0 and b % d == 0)

print(gcd_naive(84, 120), gcd(84, 120))             # 12 12
print(gcd(-84, 120), gcd(0, 7), gcd(17, 30))        # 12 7 1   17 and 30 are coprime
print(Fraction(84, 120))                            # 7/10     Fraction divides both parts by their gcd

Key takeaways

• gcd(a, b) is the largest common divisor of a and b. Coprime means gcd(a, b) = 1.
• The gcd is the product of the shared primes with their minimum exponents. This is correct, but factoring is slow.
• gcd(a, 0) = |a|, and every common divisor of a and b divides gcd(a, b).
• Standard libraries (math.gcd, BigInteger.gcd, std::gcd) use Euclid's algorithm, not factorization.

Practice

1. (Beginner) Compute gcd(48, 180) and gcd(1001, 1331) by factorization. Which pairs among 14, 15, and 21 are relatively prime? Are the three numbers pairwise relatively prime?
2. (Intermediate) Prove that gcd(n, n + 1) = 1 for every integer n, and that gcd(a, b) = gcd(a, b − a). Hint: a common divisor of two numbers divides their difference (4.1).
3. (Interview) Rotate an array of length n left by k positions in place, with O(1) extra memory, by moving elements along cycles (the "juggling" algorithm). How many independent cycles are there? Hint: the element at index i moves to index (i − k) mod n. Count how many steps it takes to return to i.

Least Common Multiple

Why. Two periodic events, one every 4 days and one every 6 days, coincide every 12 days. Adding 1/4 + 1/6 needs a common denominator, and the smallest one is 12. Scheduling, gear ratios, and synchronizing loops with different periods all need the smallest common multiple.

What. For positive integers a and b, the least common multiple lcm(a, b) is the smallest positive integer m with a ∣ m and b ∣ m. In terms of prime factorizations, it takes the maximum exponent of each prime.

                 2    3    5    7
     84   =     2² · 3¹ · 5⁰ · 7¹
    120   =     2³ · 3¹ · 5¹ · 7⁰
    lcm   =     2³ · 3¹ · 5¹ · 7¹   =  840    (maximum of each column)

Every common multiple of a and b is a multiple of lcm(a, b), so the lcm is the join in the lattice (ℤ⁺, ∣) (2.5).

  t:        0         1         2
            0123456789012345678901234
  every 4:  x   x   x   x   x   x   x
  every 6:  x     x     x     x     x
  both:     x           x           x       <- every lcm(4, 6) = 12 days

The gcd–lcm identity. For positive integers, gcd(a, b) · lcm(a, b) = a · b. For each prime, min(e, f) + max(e, f) = e + f, so the exponents on both sides agree. In practice, the lcm comes almost for free once the gcd is known:

lcm(a, b) = (a / gcd(a, b)) · b

Divide first. In fixed-width arithmetic (Java long, C uint64_t), the product a · b can overflow even when the lcm itself fits.

Several numbers. Fold pairwise: lcm(a, b, c) = lcm(lcm(a, b), c), and the same works for the gcd. The product identity, however, does not extend to three or more numbers. For (2, 2, 2), gcd · lcm = 2 · 2 = 4, but 2 · 2 · 2 = 8.

from fractions import Fraction
from functools import reduce
from math import gcd, lcm

def lcm2(a, b):
    return a // gcd(a, b) * b                      # divide first: no intermediate value exceeds the result

print(lcm2(12, 18), lcm(12, 18))                   # 36 36
print(gcd(12, 18) * lcm(12, 18) == 12 * 18)        # True
print(reduce(lcm2, [4, 6, 10, 15]))                # 60   lcm of a list, folded pairwise
print(Fraction(1, 12) + Fraction(1, 18))           # 5/36 common denominator lcm(12, 18) = 36

Key takeaways

• lcm(a, b) is the smallest positive common multiple. It takes the maximum exponent of each prime.
• For two positive integers, gcd(a, b) · lcm(a, b) = ab, so computing the lcm only requires a gcd.
• Compute a / gcd(a, b) * b to avoid intermediate overflow.
• For lists, fold pairwise. The product identity does not hold for three or more numbers.

Practice

1. (Beginner) Compute lcm(21, 6) and lcm(8, 9, 12). Two buses leave the depot together at 8:00, one every 15 minutes and the other every 25 minutes. When do they next leave together?
2. (Intermediate) Prove gcd(a, b) · lcm(a, b) = ab using prime exponents. Then find three distinct positive integers with gcd(a, b, c) · lcm(a, b, c) ≠ abc.
3. (Interview) A scheduler runs n periodic jobs with periods p₁, …, pₙ seconds, all starting at t = 0. When do all of them next run at the same moment? How do you compute this safely when the answer may not fit in 64 bits? Hint: fold lcm over the periods. Before each multiplication, check whether it would overflow, for example by comparing against Long.MAX_VALUE / b, or use arbitrary-precision integers.

Euclidean Algorithm

Why. Factoring numbers with hundreds of digits is infeasible, yet the gcd of two such numbers can be computed in microseconds. The Euclidean algorithm, described in Euclid's Elements around 300 BC, finds the gcd using only remainders, without ever factoring.

What. The algorithm rests on one lemma.

Lemma. If a = bq + r, then gcd(a, b) = gcd(b, r).

Proof. If d divides a and b, then d divides r = a − bq (4.1). If d divides b and r, then d divides a = bq + r. So the pairs (a, b) and (b, r) have exactly the same common divisors, and therefore the same greatest one. ∎

Applying the lemma with r = a mod b gives the algorithm, which you have already met as an example of recursion and termination (3.2, 3.3):

gcd(a, 0) = a
gcd(a, b) = gcd(b, a mod b)      for b > 0

It terminates because the second argument strictly decreases (a mod b < b) and stays non-negative.

   a      b      a = b·q + r
  252    105     252 = 105·2 + 42
  105     42     105 =  42·2 + 21
   42     21      42 =  21·2 + 0
   21      0     -> gcd(252, 105) = 21

Geometric picture. Tile a 252 × 105 rectangle with squares, as large as possible at each step. Two 105 × 105 squares leave a 42 × 105 strip. Two 42 × 42 squares leave a 42 × 21 strip, which two 21 × 21 squares fill exactly. So 21 is the largest square side that tiles the whole rectangle.

Efficiency. If 0 < b ≤ a, then a mod b < a/2. If b ≤ a/2, then a mod b < b ≤ a/2. Otherwise q = 1 and a mod b = a − b < a/2. So every two steps at least halve the larger argument, and the algorithm takes O(log min(a, b)) division steps. Lamé's theorem sharpens this: the number of steps is at most five times the number of decimal digits of the smaller input. The worst case is consecutive Fibonacci numbers, where every quotient is 1 (Chapter 6).

def gcd_rec(a, b):
    return a if b == 0 else gcd_rec(b, a % b)      # gcd(a, b) = gcd(b, a mod b)

def gcd_steps(a, b):
    """Iterative Euclid that also counts division steps."""
    steps = 0
    while b != 0:
        a, b = b, a % b                            # simultaneous update: a % b uses the old a and b
        steps += 1
    return a, steps

print(gcd_rec(252, 105))                           # 21
print(gcd_steps(252, 105))                         # (21, 3)
print(gcd_steps(89, 55))                           # (1, 9)   consecutive Fibonacci numbers: all quotients are 1
print(gcd_steps(2**127 - 1, 3**80))                # (1, 80)  39-digit inputs, only 80 steps

Correctness of the loop follows from the invariant gcd(a, b) = gcd(a₀, b₀) and the variant b (3.3).

Method	Number of steps	Notes
Factor both numbers	Cost of factoring: infeasible for large inputs	Also gives the lcm and the divisors
Try every candidate divisor	O(min(a, b))	Exponential in the number of digits
Repeated subtraction	O(max(a, b)) in the worst case, e.g. gcd(n, 1)	Euclid's original formulation
Euclid with mod	O(log min(a, b)) divisions	The standard method
Binary GCD (Stein)	O(log a + log b) shifts and subtractions	Avoids division, which helps on simple hardware

Key takeaways

• gcd(a, b) = gcd(b, a mod b), because the two pairs have exactly the same common divisors.
• The algorithm stops when the second argument reaches 0, and the first argument is then the gcd.
• It needs O(log min(a, b)) steps. Consecutive Fibonacci numbers are the worst case (Lamé's theorem).
• It never factors anything. This is why gcds of huge numbers are cheap even though factoring them is not.

Practice

1. (Beginner) Trace the Euclidean algorithm for gcd(414, 662) and gcd(1071, 462), writing out every line a = b·q + r.
2. (Intermediate) Prove that a mod b < a/2 whenever 0 < b ≤ a. Conclude that the algorithm performs at most 2·log₂ a + 2 division steps.
3. (Interview) Implement the gcd of two non-negative 64-bit integers without division or modulo. Hint: use binary GCD. gcd(2a, 2b) = 2·gcd(a, b), gcd(2a, b) = gcd(a, b) when b is odd, and gcd(a, b) = gcd(|a − b|, min(a, b)) when both are odd.

Extended Euclidean Algorithm

Why. The gcd tells you whether a problem like "find x with 7x ≡ 1 (mod 40)" can be solved (4.3). To actually find x, which modular inverses, RSA private keys, and the Chinese Remainder Theorem all require, we need integers s and t with s·a + t·b = gcd(a, b). The extended algorithm produces them by recording how each remainder is built from a and b.

What. Given a, b ≥ 0, the extended Euclidean algorithm returns (g, s, t) with g = gcd(a, b) = s·a + t·b. The integers s and t are called Bézout coefficients.

How: the table method. Keep rows (r, s, t) that satisfy the invariant r = s·a + t·b. Start with the rows (a, 1, 0) and (b, 0, 1), which satisfy it trivially. Each new row is previous row − q · current row, with the same quotient q that Euclid's algorithm uses. A linear combination of two rows that satisfy the invariant also satisfies it. When the remainder reaches 0, the row before it contains the gcd and its coefficients.

For a = 240 and b = 46:

    r      s      t      q     division
   240     1      0
    46     0      1      5     240 = 46·5 + 10
    10     1     -5      4      46 = 10·4 + 6
     6    -4     21      1      10 =  6·1 + 4
     4     5    -26      1       6 =  4·1 + 2
     2    -9     47      2       4 =  2·2 + 0
     0    23   -120

  gcd(240, 46) = 2 = (-9)·240 + 47·46        check: -2160 + 2162 = 2

By hand: back-substitution. Alternatively, run Euclid forward, then solve each line for its remainder and substitute upward:

  2 = 6 − 1·4
    = 6 − 1·(10 − 1·6)         = 2·6 − 1·10
    = 2·(46 − 4·10) − 1·10      = 2·46 − 9·10
    = 2·46 − 9·(240 − 5·46)     = 47·46 − 9·240

Recursive form. If gcd(b, a mod b) = s'·b + t'·(a mod b), substitute a mod b = a − ⌊a/b⌋·b and collect terms. This gives g = t'·a + (s' − ⌊a/b⌋·t')·b.

def ext_gcd(a, b):
    """Return (g, s, t) with g == gcd(a, b) == s*a + t*b, for a, b >= 0."""
    old_r, r = a, b
    old_s, s = 1, 0                                # invariant: old_r == old_s*a + old_t*b
    old_t, t = 0, 1                                #            r     == s*a     + t*b
    while r != 0:
        q = old_r // r
        old_r, r = r, old_r - q * r                # the ordinary Euclid step
        old_s, s = s, old_s - q * s                # the same row operation on the coefficients
        old_t, t = t, old_t - q * t
    return old_r, old_s, old_t

def ext_gcd_rec(a, b):
    if b == 0:
        return a, 1, 0                             # a = 1·a + 0·b
    g, s, t = ext_gcd_rec(b, a % b)                # g = s·b + t·(a mod b)
    return g, t, s - (a // b) * t                  # substitute a mod b = a − (a // b)·b

print(ext_gcd(240, 46))                            # (2, -9, 47)
print(ext_gcd_rec(240, 46))                        # (2, -9, 47)
g, s, t = ext_gcd(7, 40)
print(g, s, t, s * 7 + t * 40)                     # 1 -17 3 1

The coefficients are not unique. If (s, t) works, so does (s + k·b/g, t − k·a/g) for every integer k, because the added terms cancel: (k·b/g)·a − (k·a/g)·b = 0. The algorithm returns small coefficients, with |s| ≤ b/g and |t| ≤ a/g, and needs the same O(log min(a, b)) steps as plain Euclid.

Key takeaways

• The extended algorithm returns the gcd together with Bézout coefficients s, t such that s·a + t·b = gcd(a, b).
• Each row keeps r = s·a + t·b. Apply Euclid's row operation to the coefficients as well as to the remainders.
• It runs in the same O(log min(a, b)) steps as Euclid's algorithm.
• The coefficients are not unique. Every solution has the form (s + k·b/g, t − k·a/g).
• It is the workhorse behind modular inverses (4.3) and RSA key generation (4.4).

Practice

1. (Beginner) Use the table method to find s and t with s·99 + t·78 = gcd(99, 78). Check your answer by back-substitution.
2. (Intermediate) Prove by strong induction on b that ext_gcd_rec(a, b) returns (g, s, t) with s·a + t·b = gcd(a, b).
3. (Interview) You have two jugs of capacities a and b liters and an unlimited water supply. Can you measure exactly c liters, and how would you generate the sequence of pours? Hint: every amount you can measure is a combination x·a + y·b. Relate this to gcd(a, b), and use the extended algorithm's coefficients to decide how many times to fill each jug.

Bézout's Identity

Why. The extended algorithm shows by computation that the gcd is an integer combination of a and b. Stated as a theorem, this fact connects the gcd to prime factorization and to modular arithmetic. It proves Euclid's lemma, which uniqueness of factorization needed in 4.1, and it decides exactly when modular inverses exist (4.3).

What. Bézout's identity: if a and b are integers that are not both zero, there are integers s and t with s·a + t·b = gcd(a, b). More precisely, gcd(a, b) is the smallest positive integer of the form s·a + t·b, and the set {s·a + t·b : s, t ∈ ℤ} is exactly the set of multiples of gcd(a, b).

Proof (well-ordering). The set S = {s·a + t·b : s, t ∈ ℤ, s·a + t·b > 0} is non-empty, because it contains a² + b² (take s = a, t = b). Let d = s₀a + t₀b be its least element (3.2). Divide: a = qd + r with 0 ≤ r < d. Then r = a − q(s₀a + t₀b) = (1 − qs₀)·a + (−qt₀)·b is also a combination. If r > 0, it would be an element of S smaller than d, so r = 0 and d ∣ a. The same argument gives d ∣ b, so d ≤ gcd(a, b). Conversely, gcd(a, b) divides a and b and therefore divides d, so gcd(a, b) ≤ d. ∎

  values of 6s + 10t       t = -2    -1     0     1     2
            s = -2            -32   -22   -12    -2     8
            s = -1            -26   -16    -6     4    14
            s =  0            -20   -10     0    10    20
            s =  1            -14    -4     6    16    26
            s =  2             -8     2    12    22    32

  Every value is a multiple of 2, and 2 itself appears (s = 2, t = -1): gcd(6, 10) = 2.

Consequences.

Consequence	Statement	Proof idea
Coprimality test	gcd(a, b) = 1 if and only if s·a + t·b = 1 for some integers s, t	Any common divisor of a and b divides 1
Common divisors	d ∣ a and d ∣ b ⇒ d ∣ gcd(a, b)	d divides s·a + t·b
Euclid's lemma	p prime and p ∣ ab ⇒ p ∣ a or p ∣ b	Proof below
Generalized Euclid	a ∣ bc and gcd(a, b) = 1 ⇒ a ∣ c	c = c(s·a + t·b) = (cs)·a + t·(bc)
Linear Diophantine equations	ax + by = c has integer solutions if and only if gcd(a, b) ∣ c	The combinations are exactly the multiples of the gcd
Modular inverses	a has an inverse mod n if and only if gcd(a, n) = 1	s·a + t·n = 1 ⇒ s·a ≡ 1 (mod n) (4.3)

Proof of Euclid's lemma. Suppose p ∣ ab and p ∤ a. The only positive divisors of p are 1 and p, so gcd(p, a) = 1, and Bézout gives s·p + t·a = 1. Multiplying by b gives s·p·b + t·(ab) = b. Both terms on the left are divisible by p, so p ∣ b. ∎ This completes the proof of unique factorization in 4.1.

How: solving ax + by = c. Compute g = gcd(a, b) together with s, t. If g ∤ c, there is no solution. Otherwise, scaling by c/g gives one solution (x₀, y₀) = (s·c/g, t·c/g), and every solution has the form x = x₀ + k·(b/g), y = y₀ − k·(a/g) for an integer k.

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, s, t = ext_gcd(b, a % b)
    return g, t, s - (a // b) * t

def solve_diophantine(a, b, c):
    """One integer solution (x, y) of a*x + b*y == c, or None if there is none."""
    g, s, t = ext_gcd(a, b)
    if c % g != 0:
        return None                                # every combination is a multiple of g
    k = c // g
    return s * k, t * k                            # scale s*a + t*b == g up to c

print(solve_diophantine(6, 10, 8))                 # (8, -4)   6·8 + 10·(-4) = 8
print(solve_diophantine(6, 10, 7))                 # None      6x + 10y is always even
x0, y0 = solve_diophantine(6, 10, 8)
print([(x0 + k * 5, y0 - k * 3) for k in range(-2, 1)])   # [(-2, 2), (3, -1), (8, -4)]   step (b/g, -a/g)

Key takeaways

• gcd(a, b) = s·a + t·b for some integers s, t. It is the smallest positive combination, and the combinations are exactly the multiples of the gcd.
• ax + by = c is solvable in integers if and only if gcd(a, b) ∣ c. The solutions form a family with step (b/g, −a/g).
• Bézout's identity implies Euclid's lemma, which implies unique prime factorization.
• gcd(a, n) = 1 exactly when a is invertible modulo n. This is the bridge to modular arithmetic.

Practice

1. (Beginner) Which of these equations have integer solutions: 12x + 18y = 30, 12x + 18y = 20, 7x + 11y = 1? Find one solution of each solvable equation.
2. (Intermediate) Prove that if gcd(a, b) = 1, a ∣ c, and b ∣ c, then ab ∣ c. Hint: write c = c·(s·a + t·b). Give a counterexample when gcd(a, b) ≠ 1.
3. (Interview) A game character on an infinite one-dimensional track can jump a squares right or b squares left. Which squares can it reach from square 0, and how would you find the fewest jumps to reach a square c? Hint: the reachable squares are the multiples of gcd(a, b). Among the solution family x = x₀ + k·b/g, minimize the total number of jumps |x| + |y|.

<a id="43-modular-arithmetic"></a>

4.3 Modular Arithmetic

Modular arithmetic is arithmetic on remainders: numbers wrap around when they reach the modulus, like the hours on a clock. It is the arithmetic of fixed-width machine integers, hash tables, and circular buffers, and it underlies every public-key cryptosystem. This subchapter develops congruences, the operations they support, division through inverses, and two tools for solving and computing: the Chinese Remainder Theorem and fast exponentiation.

Congruences

Why. Often only the remainder matters: the day of the week, the bucket of a hash table, the last digit of a number, whether it is even or odd. Congruence notation lets us compute with remainders as if they were ordinary numbers, writing equations instead of applying mod at every step.

What. Let n be a positive integer, called the modulus. We say a is congruent to b modulo n, written a ≡ b (mod n), if n ∣ (a − b). The following are equivalent:

• a ≡ b (mod n)
• a mod n = b mod n, so a and b leave the same remainder
• a = b + kn for some integer k

Keep two uses of "mod" apart. a mod n is an operation that returns a number in {0, 1, …, n − 1}. a ≡ b (mod n) is a relation between two numbers, which is either true or false. For example, 17 mod 5 = 2 is a computation, and 17 ≡ 2 ≡ −3 ≡ 22 (mod 5) is a chain of true statements.

Congruence modulo n is an equivalence relation (2.5). Its equivalence classes are the residue classes [a] = {a + kn : k ∈ ℤ}, and there are exactly n of them, [0], [1], …, [n − 1]. The set ℤₙ = {0, 1, …, n − 1} contains one representative from each class, namely the least non-negative residue.

  residue class mod 5:     0     1     2     3     4
                          ...   ...   ...   ...   ...
                          -10    -9    -8    -7    -6
                           -5    -4    -3    -2    -1
                            0     1     2     3     4
                            5     6     7     8     9
                           10    11    12    13    14
                          ...   ...   ...   ...   ...

  Each column is one residue class. Numbers in the same column differ by a multiple of 5.

Analogy. A clock computes modulo 12: five hours after 9 o'clock it is 2 o'clock, because 9 + 5 = 14 ≡ 2 (mod 12). The clock forgets how many full turns the hand has made and keeps only the position.

def congruent(a, b, n):
    return (a - b) % n == 0                        # n | (a - b)

print(congruent(17, 2, 5), congruent(17, -3, 5), congruent(17, 3, 5))   # True True False
print([x for x in range(-10, 15) if x % 5 == 2])   # [-8, -3, 2, 7, 12]   the class [2] mod 5, partially listed

days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]
today = 0                                          # Monday
print(days[(today + 1000) % 7])                    # Sun   1000 = 7·142 + 6, so 1000 ≡ 6 (mod 7)

Key takeaways

• a ≡ b (mod n) means n ∣ (a − b), or equivalently that a and b leave the same remainder modulo n.
• a mod n is an operation that returns a number. ≡ (mod n) is a relation that is true or false.
• Congruence modulo n is an equivalence relation with n classes, represented by ℤₙ = {0, …, n − 1}.
• Clock arithmetic is arithmetic modulo 12.

Practice

1. (Beginner) Which of these are true: 38 ≡ 14 (mod 6), −7 ≡ 5 (mod 4), 100 ≡ 1 (mod 9)? For each true statement, write a = b + kn explicitly.
2. (Intermediate) Prove that if a ≡ b (mod n) and m ∣ n, then a ≡ b (mod m). Is the converse true?
3. (Interview) Explain why x % 2 == 1 is a buggy oddness test in Java and C, and write a version that is correct in every language. Hint: what does -3 % 2 evaluate to under truncating division (4.1)? Compare against 0 instead.

Modular Operations

Why. If only the result modulo n matters, we can reduce intermediate values at every step and keep all numbers small. This is how we find the last digits of 7¹⁰⁰ or hash a long string without big-integer arithmetic. It is valid only because congruence is compatible with addition and multiplication.

What. If a ≡ b (mod n) and c ≡ d (mod n), then

a + c ≡ b + d,     a − c ≡ b − d,     a·c ≡ b·d,     aᵏ ≡ bᵏ  (k ≥ 0)      all (mod n)

Proof for products. Write a = b + sn and c = d + tn. Then ac = bd + n(bt + ds + stn), so n ∣ (ac − bd). Sums work the same way, and powers follow by induction on k. ∎

As a result, you may reduce at any point:

(a + b) mod n = ((a mod n) + (b mod n)) mod n
(a · b) mod n = ((a mod n) · (b mod n)) mod n

So ℤₙ with addition and multiplication modulo n is a number system of its own. It satisfies the familiar laws: commutativity, associativity, distributivity, identities 0 and 1, and an additive inverse n − a for every a. Chapter 12 calls such a structure a ring.

What does not carry over.

Operation	Safe to reduce modulo n?
a + b, a − b, a · b	Yes
The base of aᵏ	Yes
The exponent of aᵏ	No. 2⁵ mod 3 = 2, but 2^(5 mod 3) = 2² = 4 ≡ 1. Exponents reduce modulo φ(n) instead (4.4)
Division a / b	No. Multiply by an inverse of b, if one exists (next topic)
Comparisons such as a < b	No. Order is not preserved

Cancellation also fails. 2·1 ≡ 2·3 (mod 4), but 1 ≢ 3 (mod 4). In ℤ₆, the product 2·3 = 6 ≡ 0 even though neither factor is 0. Such factors are called zero divisors. The multiplication table shows them:

  · mod 6 │ 0  1  2  3  4  5
  ────────┼──────────────────
     0    │ 0  0  0  0  0  0
     1    │ 0  1  2  3  4  5
     2    │ 0  2  4  0  2  4
     3    │ 0  3  0  3  0  3
     4    │ 0  4  2  0  4  2
     5    │ 0  5  4  3  2  1

  Rows 1 and 5 contain every residue exactly once: gcd(1, 6) = gcd(5, 6) = 1.
  Rows 2, 3, 4 repeat values and contain extra 0s: these elements share a factor with 6.

x = 1
for _ in range(100):
    x = x * 7 % 100                                # reduce after every multiplication, so x stays below 100
print(x, pow(7, 100) % 100)                        # 1 1   the last two digits of 7^100 are 01

def poly_hash(s, base=31, mod=1_000_000_007):
    """Polynomial string hash, reduced modulo a prime after every step (Horner's rule)."""
    h = 0
    for ch in s:
        h = (h * base + ord(ch)) % mod             # h stays below mod, so h·base fits easily in 64 bits
    return h

print(poly_hash("number theory"))                  # 171526074

Fixed-width integer arithmetic in Java, C, and most hardware is arithmetic modulo 2^w, with w = 32 or w = 64. Overflow is not an error. It is wrap-around:

int big = Integer.MAX_VALUE;                        // 2^31 - 1
System.out.println(big + 1);                        // -2147483648: int arithmetic is modulo 2^32
long p = 1_000_000_007L;
long a = 1_000_000_006L, b = 999_999_999L;          // a ≡ -1 and b ≡ -8 (mod p)
System.out.println(a * b % p);                      // 8: (-1)·(-8) = 8, and a·b < 2^63 does not overflow

Key takeaways

• Congruence is preserved by +, −, ×, and powers, so you can reduce intermediate results whenever you like.
• ℤₙ with addition and multiplication modulo n follows the usual algebraic laws, except for division.
• Cancellation fails when the cancelled factor shares a divisor with n. Such factors can be zero divisors.
• Never reduce an exponent modulo n. Fixed-width integer arithmetic is arithmetic modulo 2^w.

Practice

1. (Beginner) Compute (123·456 + 789) mod 7 without a calculator by reducing first. Find the last digit of 3²⁰²⁶.
2. (Intermediate) Prove the divisibility rule for 9: every integer is congruent modulo 9 to the sum of its decimal digits. Hint: 10 ≡ 1 (mod 9). What is the corresponding rule for 11?
3. (Interview) Compute (a · b) mod m for 64-bit unsigned a, b, m when the product overflows and no 128-bit type is available. Hint: use double-and-add, which is fast exponentiation with + in place of ×, and reduce after every doubling. Watch for overflow in x + x when m > 2⁶³.

Modular Inverses

Why. To "divide by a" modulo n, for example to solve 7x ≡ 3 (mod 40), to decrypt an affine cipher, or to compute an RSA private key, we multiply by a number that undoes multiplication by a. Unlike in the real numbers, such a number exists only for some values of a.

What. An inverse of a modulo n is an integer ā with a · ā ≡ 1 (mod n).

Theorem. a has an inverse modulo n if and only if gcd(a, n) = 1. When it exists, the inverse is unique modulo n.

Proof. If gcd(a, n) = 1, Bézout's identity (4.2) gives s·a + t·n = 1, so s·a ≡ 1 (mod n). Conversely, if a·ā ≡ 1, then a·ā − k·n = 1 for some integer k, so every common divisor of a and n divides 1. For uniqueness, suppose ab ≡ ac ≡ 1. Then b ≡ b(ac) = (ba)c ≡ c. ∎

The invertible elements of ℤₙ are called units. There are φ(n) of them (4.4). When n = p is prime, every non-zero residue is a unit, so you can divide by anything except 0. Chapter 12 calls such a structure a field.

Example. Find the inverse of 7 modulo 40. Euclid gives 40 = 7·5 + 5, 7 = 5·1 + 2, and 5 = 2·2 + 1. Back-substitution gives

  1 = 5 − 2·2 = 5 − 2·(7 − 5) = 3·5 − 2·7 = 3·(40 − 5·7) − 2·7 = 3·40 − 17·7
  so 7⁻¹ ≡ −17 ≡ 23 (mod 40)           check: 7·23 = 161 = 4·40 + 1

Method	Works when	Cost
Try x = 1, 2, …, n − 1	Any n	O(n)
Extended Euclid	gcd(a, n) = 1	O(log n)
Fermat: a^(p−2) mod p	n = p is prime	O(log p) multiplications (4.4)
Built-ins	pow(a, -1, n) in Python 3.8+, BigInteger.modInverse in Java	Library call

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, s, t = ext_gcd(b, a % b)
    return g, t, s - (a // b) * t

def mod_inverse(a, n):
    g, s, _ = ext_gcd(a % n, n)
    if g != 1:
        raise ValueError(f"{a} has no inverse mod {n} (gcd = {g})")
    return s % n                                   # s may be negative: normalize it into 0..n-1

print(mod_inverse(7, 40), 7 * 23 % 40)             # 23 1
print(pow(7, -1, 40))                              # 23   built in since Python 3.8
print({a: mod_inverse(a, 10) for a in range(10) if ext_gcd(a, 10)[0] == 1})   # {1: 1, 3: 7, 7: 3, 9: 9}
try:
    mod_inverse(6, 40)
except ValueError as e:
    print(e)                                       # 6 has no inverse mod 40 (gcd = 2)

Division is now multiplication by the inverse. For example, 7x ≡ 3 (mod 40) gives x ≡ 3·23 = 69 ≡ 29 (mod 40).

Key takeaways

• ā is an inverse of a modulo n if a·ā ≡ 1 (mod n). It exists if and only if gcd(a, n) = 1, and it is unique modulo n.
• Compute it with the extended Euclidean algorithm: take s from s·a + t·n = 1 and normalize it modulo n.
• Modulo a prime, every non-zero residue has an inverse.
• Division modulo n means multiplying by an inverse.

Practice

1. (Beginner) Find the inverses of 3 modulo 7, 5 modulo 12, and 11 modulo 26. Which of 2, 4, 13, and 25 have an inverse modulo 26?
2. (Intermediate) Show that in ℤₚ, for p prime, the only elements that are their own inverse are 1 and p − 1. Hint: x² ≡ 1 means p ∣ (x − 1)(x + 1), then apply Euclid's lemma.
3. (Interview) Precompute the inverses of all of 1, 2, …, N modulo a prime p > N in O(N) total time, for example to evaluate many binomial coefficients modulo 10⁹ + 7. Hint: write p = q·i + r with r = p mod i < i, reduce modulo p, and express inv[i] in terms of inv[r].

Linear Congruences

Why. Equations like 7x ≡ 3 (mod 40) appear when breaking or decrypting affine ciphers, in scheduling problems, and as the building block of the Chinese Remainder Theorem. Unlike a linear equation over the reals, a linear congruence can have no solution, one solution, or several, and a gcd decides which.

What. A linear congruence has the form ax ≡ b (mod n).

Theorem. Let g = gcd(a, n). The congruence has a solution if and only if g ∣ b. In that case it has exactly g solutions modulo n, spaced n/g apart.

How.

1. Compute g = gcd(a, n). If g ∤ b, stop: there is no solution.
2. Divide everything by g: a' = a/g, b' = b/g, n' = n/g. Now gcd(a', n') = 1, and ax ≡ b (mod n) holds exactly when a'x ≡ b' (mod n') does, because n ∣ (ax − b) if and only if n' ∣ (a'x − b').
3. Solve x₀ ≡ b' · (a')⁻¹ (mod n').
4. The solutions modulo n are x₀, x₀ + n', …, x₀ + (g − 1)n'.

Examples.

• 7x ≡ 3 (mod 40): g = 1, so there is exactly one solution, x ≡ 3·23 ≡ 29. Check: 7·29 = 203 = 5·40 + 3.
• 6x ≡ 4 (mod 10): g = 2 divides 4. Reduce to 3x ≡ 2 (mod 5). Since 3⁻¹ ≡ 2, x ≡ 4 (mod 5), so the solutions modulo 10 are x = 4 and x = 9.
• 6x ≡ 5 (mod 10): g = 2 does not divide 5, so there is no solution. 6x − 5 is always odd and cannot be a multiple of 10.

  x            0  1  2  3  4  5  6  7  8  9
  6x mod 10    0  6  2  8  4  0  6  2  8  4

  Only multiples of gcd(6, 10) = 2 appear, each exactly twice:
  6x ≡ 4 has 2 solutions (x = 4, 9), and 6x ≡ 5 has none.

A linear congruence is a linear Diophantine equation in disguise. ax ≡ b (mod n) holds exactly when ax + ny = b for some integer y, so the theorem is Bézout's result from 4.2.

Application: the affine cipher. Encrypt letters x ∈ ℤ₂₆ as E(x) = (ax + b) mod 26. Decryption solves ax + b ≡ y for x, which gives D(y) = a⁻¹(y − b) mod 26. This works only when gcd(a, 26) = 1. Otherwise E is not injective (2.2), and some ciphertexts have two possible plaintexts.

from math import gcd

def solve_linear_congruence(a, b, n):
    """All x in 0..n-1 with a*x ≡ b (mod n)."""
    g = gcd(a, n)
    if b % g != 0:
        return []                                  # no solutions
    a2, b2, n2 = a // g, b // g, n // g            # now gcd(a2, n2) == 1
    x0 = b2 * pow(a2, -1, n2) % n2                 # the unique solution modulo n2
    return [x0 + k * n2 for k in range(g)]         # g solutions modulo n, spaced n2 apart

print(solve_linear_congruence(7, 3, 40))           # [29]
print(solve_linear_congruence(6, 4, 10))           # [4, 9]
print(solve_linear_congruence(6, 5, 10))           # []

A, B = 5, 8                                        # key with gcd(5, 26) = 1, so E is a bijection
A_INV = pow(A, -1, 26)                             # 21, since 5·21 = 105 = 4·26 + 1

def encrypt(text):
    return "".join(chr((A * (ord(c) - 65) + B) % 26 + 65) for c in text)

def decrypt(text):
    return "".join(chr(A_INV * (ord(c) - 65 - B) % 26 + 65) for c in text)

print(encrypt("ATTACK"), decrypt(encrypt("ATTACK")))   # IZZISG ATTACK

Key takeaways

• ax ≡ b (mod n) is solvable if and only if g = gcd(a, n) divides b.
• When it is solvable, there are exactly g solutions modulo n, spaced n/g apart.
• To solve it, divide through by g, then multiply by the inverse of a/g modulo n/g.
• A linear congruence is equivalent to the Diophantine equation ax + ny = b.

Practice

1. (Beginner) Solve 3x ≡ 4 (mod 7), 4x ≡ 6 (mod 10), and 4x ≡ 5 (mod 10).
2. (Intermediate) An affine cipher E(x) = (ax + b) mod 26 encrypts E (4) as R (17) and T (19) as C (2). Recover the key (a, b) by solving the resulting system of two linear congruences.
3. (Interview) A linear congruential generator xₖ₊₁ = (a·xₖ + c) mod m with known m leaks three consecutive outputs x₀, x₁, x₂. How do you recover a and c, and when is the answer not unique? Hint: subtracting consecutive equations gives x₂ − x₁ ≡ a·(x₁ − x₀) (mod m), which is a linear congruence in a.

Chinese Remainder Theorem

Why. A puzzle from Sunzi's Mathematical Classic (3rd–5th century) asks for a number that leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7. The same problem appears in modern practice. Computing modulo a large n = pq is cheaper if you work modulo p and modulo q separately and then recombine, which makes RSA decryption about four times faster. Big-number libraries also split arithmetic across several small moduli. The Chinese Remainder Theorem (CRT) says when and how the pieces combine.

What. Let m₁, …, mₖ be pairwise relatively prime positive integers and M = m₁m₂⋯mₖ. For any integers a₁, …, aₖ, the system

x ≡ a₁ (mod m₁),   x ≡ a₂ (mod m₂),   …,   x ≡ aₖ (mod mₖ)

has a solution, and the solution is unique modulo M.

Construction. Let Mᵢ = M / mᵢ. Since Mᵢ is a product of moduli that are all coprime to mᵢ, gcd(Mᵢ, mᵢ) = 1, and yᵢ = Mᵢ⁻¹ mod mᵢ exists. Then

x = a₁M₁y₁ + a₂M₂y₂ + ⋯ + aₖMₖyₖ   (mod M)

works. Modulo mⱼ, every term with i ≠ j vanishes because mⱼ ∣ Mᵢ, and the j-th term is aⱼ·Mⱼyⱼ ≡ aⱼ·1. For uniqueness, if x and x' are both solutions, then every mᵢ divides x − x'. Since the moduli are pairwise coprime, their product M divides x − x'. For two moduli, write x − x' = m₁k. Then m₂ ∣ m₁k and gcd(m₁, m₂) = 1, so m₂ ∣ k by the generalized Euclid's lemma (4.2), and m₁m₂ ∣ x − x'. Induction extends this to k moduli.

Sunzi's puzzle. Here m = (3, 5, 7), M = 105, and a = (2, 3, 2).

  i   mᵢ   Mᵢ = 105/mᵢ   Mᵢ mod mᵢ   yᵢ = Mᵢ⁻¹ mod mᵢ   aᵢ·Mᵢ·yᵢ
  1    3       35            2              2              2·35·2 = 140
  2    5       21            1              1              3·21·1 =  63
  3    7       15            1              1              2·15·1 =  30
                                                      sum = 233 ≡ 23 (mod 105)

  check: 23 = 3·7 + 2 = 5·4 + 3 = 7·3 + 2

By successive substitution, which is often easier by hand: x ≡ 2 (mod 3) means x = 2 + 3k. Then 2 + 3k ≡ 3 (mod 5) gives 3k ≡ 1, so k ≡ 2 (mod 5) and x = 8 + 15j. Finally 8 + 15j ≡ 2 (mod 7) gives 1 + j ≡ 2, so j ≡ 1 and x = 23.

The structural view. The map x ↦ (x mod m₁, …, x mod mₖ) is a bijection from ℤ_M to ℤ_{m₁} × ⋯ × ℤ_{mₖ} (2.2). Addition and multiplication can be carried out on each component separately. This representation is called a residue number system. Coprimality is essential:

  x            0      1      2      3      4      5
  x mod 2      0      1      0      1      0      1
  x mod 3      0      1      2      0      1      2
  pair       (0,0)  (1,1)  (0,2)  (1,0)  (0,1)  (1,2)    all 6 pairs appear once: ℤ₆ ↔ ℤ₂ × ℤ₃

  x            0      1      2      3
  pair       (0,0)  (1,1)  (0,0)  (1,1)                  moduli 2 and 2 are not coprime: ℤ₄ is not ℤ₂ × ℤ₂

Moduli that are not coprime. The system x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂) is solvable if and only if a₁ ≡ a₂ (mod gcd(m₁, m₂)). In that case, the solution is unique modulo lcm(m₁, m₂).

from math import prod

def crt(residues, moduli):
    """Solve x ≡ a_i (mod m_i) for pairwise coprime m_i. Returns (x, M) with 0 <= x < M."""
    M = prod(moduli)
    x = 0
    for a_i, m_i in zip(residues, moduli):
        M_i = M // m_i                             # divisible by every other modulus
        y_i = pow(M_i, -1, m_i)                    # exists because gcd(M_i, m_i) = 1
        x += a_i * M_i * y_i                       # ≡ a_i (mod m_i) and ≡ 0 modulo every other m_j
    return x % M, M

print(crt([2, 3, 2], [3, 5, 7]))                   # (23, 105)
print(crt([1, 2, 3, 4], [5, 7, 9, 11]))            # (1731, 3465)

# Residue number system: multiply via small residues, then reconstruct the product once
mods = [999_983, 999_979, 999_961]                 # pairwise coprime (all prime), M ≈ 10^18
a, b = 123_456_789, 987_654_321
rc = [(a % m) * (b % m) % m for m in mods]         # three independent small multiplications
print(crt(rc, mods)[0] == a * b)                   # True: a·b < M, so the product is recovered exactly

Key takeaways

• With pairwise coprime moduli, a system of congruences has exactly one solution modulo M = ∏ mᵢ.
• Construct it as x = Σ aᵢ·Mᵢ·(Mᵢ⁻¹ mod mᵢ), or by substituting one congruence into the next.
• ℤ_M corresponds to ℤ_{m₁} × ⋯ × ℤ_{mₖ}: compute on each component separately and recombine once at the end.
• For moduli that are not coprime, the congruences must agree modulo the gcd, and the solution is unique modulo the lcm.

Practice

1. (Beginner) Solve x ≡ 1 (mod 4), x ≡ 3 (mod 5), x ≡ 2 (mod 3) with the construction, then check your answer by substitution.
2. (Intermediate) Show that x ≡ 3 (mod 6), x ≡ 4 (mod 8) has no solution, while x ≡ 3 (mod 6), x ≡ 7 (mod 8) does. Find all its solutions modulo 24.
3. (Interview) RSA decryption computes c^d mod n with n = pq. Explain how the CRT speeds this up and estimate the gain. Hint: compute modulo p and modulo q with exponents d mod (p − 1) and d mod (q − 1) (Fermat, 4.4). The numbers are half as long, and multiplication cost grows roughly quadratically with length.

Fast Modular Exponentiation

Why. RSA, Diffie–Hellman key exchange, and primality tests all compute aᵉ mod n with numbers hundreds of digits long. Computing aᵉ first is impossible: with a 2048-bit exponent, the result would have far more digits than there are atoms in the universe. Multiplying e times is also far too slow. Two ideas solve the problem: reduce modulo n after every multiplication (previous topic), and use the square-and-multiply method from 3.3, which needs only O(log e) multiplications.

What. Write the exponent in binary, e = Σ bᵢ·2ⁱ. Then

aᵉ = ∏ over the bits bᵢ = 1 of  a^(2ⁱ)

and the powers a, a², a⁴, a⁸, … each come from squaring the previous one, all modulo n.

Example. Compute 3¹³ mod 100, the same power as in 3.3, where 3¹³ = 1594323. Here 13 = 1101₂.

  bit i   bᵢ   a^(2ⁱ) mod 100        result (mod 100)
    0     1    3                     1 · 3   =  3
    1     0    3²  =  9              3            (bit is 0: unchanged)
    2     1    9²  = 81              3 · 81  = 243  ≡ 43
    3     1    81² = 6561 ≡ 61       43 · 61 = 2623 ≡ 23

  3¹³ ≡ 23 (mod 100)           check: 1594323 ends in 23

def mod_pow(a, e, n):
    """Compute a**e mod n for e >= 0 with O(log e) multiplications of numbers below n."""
    result = 1 % n                                 # 1 % n handles n == 1 correctly
    a %= n
    while e > 0:
        if e & 1:                                  # the lowest remaining bit of e is 1
            result = result * a % n                # include the current power a^(2^i)
        a = a * a % n                              # a^(2^i) -> a^(2^(i+1))
        e >>= 1                                    # move on to the next bit
    return result

print(mod_pow(3, 13, 100))                         # 23
print(mod_pow(2, 10**18, 10**9 + 7) == pow(2, 10**18, 10**9 + 7))   # True, after only 60 squarings

JavaScript's Number loses precision above 2⁵³, so products of large residues must use BigInt:

function modPow(a, e, n) {
  let result = 1n % n;
  a %= n;
  while (e > 0n) {
    if (e & 1n) result = (result * a) % n;   // BigInt arithmetic: exact, with no overflow
    a = (a * a) % n;
    e >>= 1n;
  }
  return result;
}

console.log(modPow(3n, 13n, 100n));                          // 23n
console.log(modPow(2n, 10n ** 18n, 1_000_000_007n) > 0n);    // true

Correctness follows from the same invariant as power_iter in 3.3, now read modulo n: result · aᵉ ≡ a₀^e₀ (mod n).

Approach	Multiplications	Size of intermediate values
Compute aᵉ, then reduce	e − 1	Grows to about e·log₂ a bits
Multiply e times, reducing each step	e − 1	Below n²
Square-and-multiply, reducing each step	At most 2·log₂ e	Below n²

For a 2048-bit exponent, that is at most about 4096 multiplications instead of about 2²⁰⁴⁸. Use the built-ins in practice: pow(a, e, n) in Python and BigInteger.modPow in Java. Cryptographic code also needs constant-time variants such as the Montgomery ladder, because the branch on each bit of e leaks the secret exponent through timing.

Key takeaways

• Never compute aᵉ and then reduce. Reduce after every multiplication.
• Square-and-multiply follows the binary digits of e and needs at most 2·log₂ e multiplications.
• The invariant result · baseᵉ ≡ aᵉ (mod n) gives the same correctness proof as in 3.3.
• Use library functions. In cryptography, use constant-time implementations.

Practice

1. (Beginner) Compute 7²² mod 11 by hand with square-and-multiply, using 22 = 10110₂. Show the table.
2. (Intermediate) Write the left-to-right variant, which scans the bits of e from the most significant one and, for each bit, squares result and then multiplies by a if the bit is 1. Prove it correct with an invariant about the prefix of bits processed so far.
3. (Interview) Compute the n-th Fibonacci number modulo 10⁹ + 7 for n up to 10¹⁸. Hint: square-and-multiply works for any associative multiplication. Apply it to the matrix [[1, 1], [1, 0]].

<a id="44-applications-of-number-theory"></a>

4.4 Applications of Number Theory

This subchapter turns the tools of 4.1–4.3 into results that are used every day. Fermat's and Euler's theorems shrink huge exponents and power primality tests. Positional number systems explain how machines store integers. Check digits and hash functions are modular arithmetic in disguise. RSA combines almost every topic in this chapter.

Fermat's Little Theorem

Why. Powers modulo a prime repeat in cycles. Knowing the cycle length lets us shrink enormous exponents and compute inverses by exponentiation. Most importantly, it lets us test 1000-bit numbers for primality, which is hopeless with trial division.

What. Fermat's little theorem (1640): if p is prime and p ∤ a, then a^(p−1) ≡ 1 (mod p). An equivalent form is aᵖ ≡ a (mod p) for every integer a, including multiples of p.

Proof. Consider the p − 1 numbers a, 2a, 3a, …, (p − 1)a modulo p. None of them is ≡ 0, because p ∤ i and p ∤ a, so p ∤ ia by Euclid's lemma. They are pairwise distinct: if ia ≡ ja, then p ∣ (i − j)a, so p ∣ i − j, and therefore i = j. So they are the numbers 1, 2, …, p − 1 in some order. Multiplying all of them gives a^(p−1)·(p − 1)! ≡ (p − 1)! (mod p). Since (p − 1)! is coprime to p, we can cancel it by multiplying by its inverse. ∎

  p = 7, a = 3:
  i           1  2  3  4  5  6
  3i mod 7    3  6  2  5  1  4       the same six residues, in a different order

  multiply each row:   3⁶ · 6!  ≡  6!  (mod 7)   ⇒   3⁶ ≡ 1 (mod 7)

Consequences.

Use	Statement	Example
Shrink exponents	aᵉ ≡ a^(e mod (p−1)) (mod p) when p ∤ a	3¹⁰⁰ mod 7: 100 mod 6 = 4, and 3⁴ = 81 ≡ 4
Inverses	a⁻¹ ≡ a^(p−2) (mod p)	3⁻¹ ≡ 3⁵ = 243 ≡ 5 (mod 7), and 3·5 = 15 ≡ 1
Primality test	If a^(n−1) ≢ 1 (mod n) for some a with gcd(a, n) = 1, then n is certainly composite	2⁸ mod 9 = 4 ≠ 1, so 9 is composite

Exponents shrink modulo p − 1, not modulo p, as warned in 4.3.

The Fermat primality test and its limits. Pick random bases a. If any of them gives a^(n−1) ≢ 1 (mod n), then a is a Fermat witness and n is composite. If all of them pass, n is probably prime. The converse of the theorem is false, however:

• 341 = 11·31 satisfies 2³⁴⁰ ≡ 1 (mod 341), so it is a pseudoprime to base 2.
• Carmichael numbers, the smallest of which is 561 = 3·11·17, pass the test for every base coprime to them.

The Miller–Rabin test strengthens the Fermat test and has no analogue of Carmichael numbers. For any odd composite n, at least 3/4 of the bases expose it, so 40 random rounds leave an error probability of at most 4⁻⁴⁰. Cryptographic libraries use this test to generate RSA primes.

import random
from math import gcd

print(pow(3, 6, 7), pow(3, 100, 7), pow(3, 100 % 6, 7))   # 1 4 4

def fermat_test(n, trials=20):
    """False: n is certainly composite. True: n is probably prime."""
    if n < 4:
        return n in (2, 3)
    for _ in range(trials):
        a = random.randrange(2, n - 1)
        if pow(a, n - 1, n) != 1:
            return False                           # a is a Fermat witness, so n is composite
    return True

print(fermat_test(1_000_003), fermat_test(1_000_001))     # True False
print(pow(2, 340, 341))                                   # 1: base 2 is fooled by 341 = 11 · 31
print(all(pow(a, 560, 561) == 1 for a in range(2, 561) if gcd(a, 561) == 1))   # True: 561 fools every coprime base

Key takeaways

• If p is prime and p ∤ a, then a^(p−1) ≡ 1 (mod p).
• Reduce exponents modulo p − 1, not modulo p. The inverse of a is a^(p−2).
• The Fermat test can prove that a number is composite, but it can only suggest that a number is prime. Pseudoprimes and Carmichael numbers fool it.
• In practice, use Miller–Rabin, which has a provably small error probability.

Practice

1. (Beginner) Compute 2¹⁰⁰ mod 11 and 5²⁰²⁶ mod 13 with Fermat's little theorem.
2. (Intermediate) Prove that n⁷ − n is divisible by 42 for every integer n. Hint: prove divisibility by 2, 3, and 7 separately using aᵖ ≡ a (mod p), then combine the three results because the factors are pairwise coprime.
3. (Interview) A deterministic polynomial-time primality test (AKS, 2002) exists. Why do real systems still use probabilistic Miller–Rabin? Hint: compare running times in practice, and compare an error probability of 4⁻⁴⁰ with the probability of a hardware fault during the computation.

Euler's Totient Function

Why. Fermat's theorem covers only prime moduli, but RSA works modulo n = pq. To generalize the theorem, we need to know how many residues modulo n are invertible. That count is φ(n). It also counts the fractions k/n already in lowest terms, and it is the size of the group of units in Chapter 12.

What. Euler's totient function φ(n) is the number of integers k in {1, 2, …, n} with gcd(k, n) = 1. Equivalently, it is the number of units of ℤₙ (4.3). For example, φ(1) = 1.

  k             1  2  3  4  5  6  7  8  9 10 11 12
  gcd(k, 12)    1  2  3  4  1  6  1  4  3  2  1 12
  coprime       *           *     *           *

  φ(12) = 4: the units of ℤ₁₂ are 1, 5, 7, 11

How: formulas from the factorization.

Case	φ(n)	Reason
p prime	p − 1	Every integer 1, …, p − 1 is coprime to p
Prime power pᵏ	pᵏ − pᵏ⁻¹ = pᵏ⁻¹(p − 1)	Remove the pᵏ⁻¹ multiples of p
gcd(m, n) = 1	φ(mn) = φ(m)·φ(n)	By the CRT, x is a unit modulo mn exactly when it is a unit modulo m and modulo n
General n	n · ∏ (1 − 1/p) over the primes p ∣ n	Combine the rows above with the factorization of n
n = pq, distinct primes	(p − 1)(q − 1)	Used in RSA

For example, φ(36) = 36·(1 − 1/2)·(1 − 1/3) = 12, and φ(12) = 12·(1/2)·(2/3) = 4.

from math import gcd

def phi_naive(n):
    return sum(1 for k in range(1, n + 1) if gcd(k, n) == 1)   # direct count, fine for small checks

def phi(n):
    """Euler's totient via n · ∏ (1 - 1/p), factoring n by trial division."""
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p                            # strip every factor p
            result -= result // p                  # result *= (1 - 1/p), in exact integer arithmetic
        p += 1
    if n > 1:
        result -= result // n                      # at most one prime factor > √n can remain
    return result

print([phi(n) for n in range(1, 13)])              # [1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4]
print(phi(36), phi_naive(36))                      # 12 12
print(phi(61 * 53), 60 * 52)                       # 3120 3120   φ(pq) = (p − 1)(q − 1)

Computing φ is as hard as factoring. The formula needs the prime factors of n. For n = pq, knowing φ(n) is enough to recover p and q: since φ(n) = n − (p + q) + 1, you know p + q and pq, and p and q are the roots of a quadratic equation. This is exactly why RSA can publish n but must keep φ(n) secret.

Key takeaways

• φ(n) counts the integers in 1..n that are coprime to n, which is the number of invertible residues modulo n.
• φ(p) = p − 1, φ(pᵏ) = pᵏ⁻¹(p − 1), and φ(mn) = φ(m)φ(n) when gcd(m, n) = 1.
• In general, φ(n) = n·∏(1 − 1/p), which requires the prime factorization of n.
• For n = pq, knowing φ(n) is equivalent to knowing the factors p and q.

Practice

1. (Beginner) Compute φ(15), φ(16), φ(17), and φ(100), and list the units modulo 15.
2. (Intermediate) Verify that Σ φ(d) = 12, where the sum runs over the positive divisors d of 12, and explain why this holds for every n. Hint: write each fraction k/12 for k = 1, …, 12 in lowest terms and group the fractions by their reduced denominator.
3. (Interview) Given an RSA modulus n = pq and the value φ(n), recover p and q using a constant number of arithmetic operations and one integer square root. Hint: find p + q, then solve x² − (p + q)x + n = 0.

Euler's Theorem

Why. RSA decryption works because raising a message to the power e and then to the power d returns the original message modulo n = pq, which is not prime. Euler's theorem generalizes Fermat's theorem to any modulus and explains why this works.

What. Euler's theorem: if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n). For a prime n = p, φ(p) = p − 1, which gives Fermat's little theorem.

Proof. This is Fermat's proof with the units in place of 1, …, p − 1. Let r₁, …, r_φ(n) be the units modulo n. Multiplying by the unit a maps units to units, and different units to different units, because a can be cancelled. So ar₁, …, ar_φ(n) is a rearrangement of r₁, …, r_φ(n). Multiplying everything together gives a^φ(n) · ∏ rᵢ ≡ ∏ rᵢ. The product ∏ rᵢ is a unit, so it can be cancelled. ∎ In the language of Chapter 12, this is Lagrange's theorem applied to the group of units.

  n = 10, a = 3:
  unit r         1  3  7  9
  3r mod 10      3  9  1  7       a rearrangement of the units

  ⇒  3^φ(10) = 3⁴ = 81 ≡ 1 (mod 10)

Consequences.

• Shrink exponents: aᵉ ≡ a^(e mod φ(n)) (mod n) when gcd(a, n) = 1. For example, the last digit of 7²²²: φ(10) = 4 and 222 mod 4 = 2, so 7²²² ≡ 7² = 49 ≡ 9 (mod 10).
• Inverses: a⁻¹ ≡ a^(φ(n)−1) (mod n).
• Orders: the smallest k > 0 with aᵏ ≡ 1 divides φ(n), and it can be smaller. For example, 9² = 81 ≡ 1 (mod 10), while φ(10) = 4.

Coprimality matters. The theorem can fail when gcd(a, n) > 1: 2^φ(10) = 2⁴ = 16 ≡ 6 (mod 10). For a squarefree modulus n = pq, a slightly different statement holds for every a, and this is what RSA needs.

RSA lemma. If p ≠ q are primes, n = pq, and k ≥ 0, then a^(k·φ(n) + 1) ≡ a (mod n) for every integer a.

Proof. Work modulo p. If p ∣ a, both sides are ≡ 0. Otherwise a^(kφ(n)) = (a^(p−1))^(k(q−1)) ≡ 1 by Fermat, so the left side is ≡ a. The same argument works modulo q. Both congruences hold, so by the CRT (4.3) the congruence holds modulo pq. ∎

from math import gcd

n = 10
units = [r for r in range(1, n) if gcd(r, n) == 1]
print(units, sorted(3 * r % n for r in units))     # [1, 3, 7, 9] [1, 3, 7, 9]
print(pow(7, 222, 10), pow(7, 222 % 4, 10))        # 9 9   exponent reduced modulo φ(10) = 4
print(pow(2, 4, 10))                               # 6     gcd(2, 10) ≠ 1, so Euler does not apply

p, q = 11, 13                                      # RSA lemma: holds for every a, even multiples of p or q
n, phi_n = p * q, (p - 1) * (q - 1)
print(all(pow(a, 3 * phi_n + 1, n) == a for a in range(n)))   # True

Key takeaways

• If gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n). Fermat's little theorem is the special case of a prime modulus.
• For bases coprime to n, reduce exponents modulo φ(n).
• The theorem needs gcd(a, n) = 1, but for n = pq the RSA lemma a^(kφ(n)+1) ≡ a holds for every a.
• The order of a unit divides φ(n).

Practice

1. (Beginner) Find the last digit of 3¹⁰⁰⁰ and the last two digits of 7²⁰²⁶.
2. (Intermediate) Let gcd(a, n) = 1 and let k be the smallest positive integer with aᵏ ≡ 1 (mod n). Prove that k ∣ φ(n). Hint: divide φ(n) by k and show that the remainder must be 0.
3. (Interview) Compute a^(b^c) mod m for a prime m and very large a, b, c. Hint: reduce the exponent b^c modulo m − 1 with fast modular exponentiation. Treat a ≡ 0 (mod m) as a special case.

Integer Representations and Bases

Why. Computers store integers in binary, programmers read them in hexadecimal, and people use decimal. Converting between bases, reasoning about bit widths, and understanding negative machine integers all rest on the division algorithm. Square-and-multiply (4.3) and binary GCD (4.2) work directly on base-2 digits.

What. Let b ≥ 2. Every positive integer n can be written uniquely as

n = aₖbᵏ + aₖ₋₁bᵏ⁻¹ + ⋯ + a₁b + a₀      with digits 0 ≤ aᵢ < b and aₖ ≠ 0

This is written (aₖaₖ₋₁…a₁a₀)_b. Existence and uniqueness follow from the division algorithm. The last digit a₀ must be n mod b, the remaining digits represent n div b, and induction finishes the argument.

n has ⌊log_b n⌋ + 1 digits in base b. A number has about log₂ 10 ≈ 3.32 times as many binary digits as decimal digits.

Base	Name	Digits	Literal in Python	Typical use
2	Binary	0, 1	0b11110101	Hardware, bit manipulation
8	Octal	0–7	0o365	Unix file permissions (chmod 755)
10	Decimal	0–9	245	People
16	Hexadecimal	0–9, A–F	0xF5	Bytes, memory addresses, colors (#FF8800)
64	Base64	A–Z, a–z, 0–9, +, /	(encoding only)	Binary data inside text formats

Because 16 = 2⁴ and 8 = 2³, each hexadecimal digit corresponds to exactly 4 bits and each octal digit to 3 bits. For example, 0xF5 = 1111 0101.

How. To convert to base b, divide repeatedly. The remainders are the digits, from least significant to most significant. To convert from base b, use Horner's rule: n = (⋯((aₖ·b + aₖ₋₁)·b + aₖ₋₂)⋯)·b + a₀.

  245 ÷ 2 = 122  r 1    <- a₀ (least significant)
  122 ÷ 2 =  61  r 0
   61 ÷ 2 =  30  r 1
   30 ÷ 2 =  15  r 0
   15 ÷ 2 =   7  r 1
    7 ÷ 2 =   3  r 1
    3 ÷ 2 =   1  r 1
    1 ÷ 2 =   0  r 1    <- a₇ (most significant)

  Read upward: 245 = (11110101)₂ = (F5)₁₆ = (365)₈

Two's complement. A w-bit signed integer is an element of ℤ_{2^w} (4.3) with representatives −2^(w−1), …, 2^(w−1) − 1. The negative number −x is stored as the bit pattern of 2^w − x. With w = 8, the value −11 is stored as 256 − 11 = 245 = 11110101, which is the pattern converted above. Read as unsigned, the 8 bits mean 245. Read as signed, they mean −11. The two readings are congruent modulo 256, which is why the hardware can use the same addition circuit for both.

DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def to_base(n, b):
    """Digits of n >= 0 in base b, 2 <= b <= 36, by repeated division."""
    if n == 0:
        return "0"
    out = []
    while n > 0:
        n, r = divmod(n, b)                        # r is the next digit, least significant first
        out.append(DIGITS[r])
    return "".join(reversed(out))

def from_base(s, b):
    n = 0
    for ch in s:
        n = n * b + DIGITS.index(ch)               # Horner's rule: shift left one digit, then add the new one
    return n

print(to_base(245, 2), to_base(245, 16), to_base(245, 8))   # 11110101 F5 365
print(from_base("11110101", 2), int("F5", 16))              # 245 245
print(-11 & 0xFF, format(-11 & 0xFF, "08b"))                # 245 11110101   8-bit two's complement of -11
print((245).bit_length(), len(str(2**64)))                  # 8 20

System.out.println(Integer.toBinaryString(245));   // 11110101
System.out.println(Integer.parseInt("F5", 16));    // 245
System.out.println((byte) 245);                     // -11: the same 8 bits read as a signed byte

Key takeaways

• Every positive integer has a unique representation in each base b ≥ 2. Repeated division produces the digits from least significant to most significant, and Horner's rule converts back.
• n has ⌊log_b n⌋ + 1 digits in base b, and about 3.32 bits per decimal digit.
• Hexadecimal and octal digits correspond to groups of 4 and 3 bits.
• Two's complement treats w-bit integers as ℤ_{2^w} with representatives centered on 0. −x is stored as 2^w − x.

Practice

1. (Beginner) Convert 2026 to binary, octal, and hexadecimal. Convert (1A3)₁₆ and (777)₈ to decimal.
2. (Intermediate) Prove that 2ᵏ ∣ n if and only if the last k binary digits of n are 0, and that n mod 2ᵏ = n & (2ᵏ − 1) for n ≥ 0. Explain why hash tables with m = 2ᵏ buckets compute the bucket as h & (m − 1).
3. (Interview) Convert an integer to base −2 (negabinary), which represents negative numbers without a sign. Hint: the division algorithm still works with b = −2 if you insist on remainders in {0, 1}. When your language returns a negative remainder, adjust the remainder and the quotient.

Hashing and Check Digits

Why. A hash table must spread an enormous key space evenly over m buckets, and must do so quickly. Identifiers such as ISBNs, credit card numbers, and IBANs must catch typing mistakes. Both are applications of modular arithmetic. A hash is typically "something mod m", and a check digit is chosen so that a weighted sum of the digits is ≡ 0 modulo some m.

What: hashing. A hash function maps keys to bucket indices, h: K → {0, …, m − 1}. The division method uses h(k) = k mod m, and the choice of m matters.

Consider keys that form an arithmetic progression k, k + d, k + 2d, …, such as aligned memory addresses or IDs that grow in steps. Their buckets cycle through only m / gcd(d, m) distinct values, by the linear congruence theorem (4.3). If m is a power of 2 and d is even, most buckets are never used. If m is prime, gcd(d, m) = 1 for every stride d < m, and every bucket is used.

  key:          0  4  8 12 16 20 24 28 32 36
  key mod 8:    0  4  0  4  0  4  0  4  0  4     only 8 / gcd(4, 8) = 2 buckets are used
  key mod 7:    0  4  1  5  2  6  3  0  4  1     all 7 buckets are used (gcd(4, 7) = 1)

For strings, the polynomial hash h(s) = (s₀B^(L−1) + s₁B^(L−2) + ⋯ + s_(L−1)) mod p is evaluated with Horner's rule and reduced at each step (4.3). Universal hashing picks h(k) = ((a·k + b) mod p) mod m with random a and b, so no fixed set of keys is bad for every choice. For any two distinct keys, the collision probability is at most about 1/m (stated here without proof).

What: check digits. Append a digit chosen so that a weighted sum of all digits is ≡ 0 (mod m). A typing error that changes the sum's residue is detected.

ISBN-10. The digits x₁x₂…x₁₀ must satisfy 1·x₁ + 2·x₂ + ⋯ + 10·x₁₀ ≡ 0 (mod 11), where the check digit x₁₀ may be X, meaning 10. Because 11 is prime, this scheme detects:

• Every single-digit error. Changing xᵢ by δ ≠ 0 changes the sum by i·δ. Both i and δ are non-zero modulo 11, so their product is too (Euclid's lemma).
• Every transposition of two digits, adjacent or not. Swapping xᵢ and xⱼ changes the sum by (j − i)(xᵢ − xⱼ), which is non-zero modulo 11 unless the two digits are equal.

Because 10 ≡ −1 (mod 11), the check digit is simply x₁₀ = (1·x₁ + ⋯ + 9·x₉) mod 11. For 0-306-40615-?, the weighted sum is 0 + 6 + 0 + 24 + 20 + 0 + 42 + 8 + 45 = 145, and 145 mod 11 = 2, which gives ISBN 0-306-40615-2.

Scheme	Modulus	Weights	Single-digit errors	Adjacent transpositions
ISBN-10	11	1, 2, …, 10	All detected	All detected
ISBN-13 / EAN-13 barcodes	10	1, 3, 1, 3, …	All detected	Missed when the two digits differ by 5
Luhn (credit cards, IMEI)	10	1, 2, 1, 2, … from the right, summing the digits of doubled values	All detected	Missed only for 09 ↔ 90
IBAN (ISO 7064)	97	Powers of 10 (the whole number must be ≡ 1 (mod 97))	All detected	All detected

A prime modulus makes every non-zero weight invertible, which is why the mod-11 and mod-97 schemes catch strictly more errors than the mod-10 schemes.

def isbn10_check_digit(first9):
    s = sum(i * int(d) for i, d in enumerate(first9, start=1))   # weights 1..9
    c = s % 11                                     # need s + 10·c ≡ 0 and 10 ≡ -1 (mod 11), so c ≡ s
    return "X" if c == 10 else str(c)

def luhn_valid(number):
    total = 0
    for i, ch in enumerate(reversed(number)):
        d = int(ch)
        if i % 2 == 1:                             # double every second digit, counting from the right
            d *= 2
            if d > 9:
                d -= 9                             # same as adding the two digits of d
        total += d
    return total % 10 == 0

print(isbn10_check_digit("030640615"))             # 2      ISBN 0-306-40615-2
print(luhn_valid("79927398713"), luhn_valid("79927398731"))   # True False   last two digits swapped

keys = range(0, 400, 4)                            # 100 keys with stride 4
print(sorted({k % 8 for k in keys}), len({k % 7 for k in keys}))   # [0, 4] 7

Key takeaways

• Division hashing uses h(k) = k mod m. Keys with stride d reach only m / gcd(d, m) buckets, and a prime m avoids this problem.
• String hashes are polynomials evaluated modulo a prime with Horner's rule. Universal hashing randomizes the coefficients.
• A check digit forces a weighted digit sum to be ≡ 0 (mod m).
• A prime modulus (11, 97) catches every single-digit error and every transposition. Mod-10 schemes miss some transpositions.

Practice

1. (Beginner) Compute the ISBN-10 check digit for 0-19-853453-?, and check whether 4111 1111 1111 1111 passes the Luhn test.
2. (Intermediate) Prove that ISBN-10 detects every transposition of two digits, adjacent or not. Then find an adjacent transposition that the EAN-13 scheme (weights 1, 3) fails to detect.
3. (Interview) A hash table with m = 2²⁰ buckets and h(k) = k mod m stores objects keyed by their memory addresses, which are multiples of 16, and shows heavy collisions. Explain why, and propose two fixes. Hint: compute gcd(16, 2²⁰). Consider multiplying by a large odd constant and keeping the high bits (Fibonacci hashing), or using a prime number of buckets.

RSA Cryptography

Why. Two parties who have never met want to communicate secretly over a public network. A symmetric cipher would require them to share a secret key first, which is the very problem they are trying to solve. Public-key cryptography removes this requirement: anyone can encrypt with a published key, but only the owner of the matching private key can decrypt. RSA (Rivest, Shamir, Adleman, 1977) was the first practical scheme. It is built entirely from this chapter: primes, gcds, modular inverses, fast exponentiation, Euler's theorem, and the presumed difficulty of factoring.

What.

Key generation.

1. Choose two large distinct primes p and q, typically 1024 bits each, by random sampling and primality testing (4.1, Fermat's little theorem above).
2. Compute n = pq, the public modulus, and φ(n) = (p − 1)(q − 1).
3. Choose a public exponent e with 1 < e < φ(n) and gcd(e, φ(n)) = 1. A common choice is e = 65537.
4. Compute the private exponent d = e⁻¹ mod φ(n) with the extended Euclidean algorithm (4.2).

The public key is (n, e). The private key is d, and p, q, and φ(n) must also stay secret.

Encryption of a message M ∈ {0, …, n − 1}: C = Mᵉ mod n. Decryption: M = Cᵈ mod n. Both use fast modular exponentiation (4.3).

Correctness. Since ed ≡ 1 (mod φ(n)), we can write ed = 1 + kφ(n). Then Cᵈ ≡ M^(ed) = M^(1 + kφ(n)) ≡ M (mod n) by the RSA lemma in Euler's theorem above, for every M.

           Bob (key owner)                                        Alice (sender)
  secret primes p, q  ─►  n = p·q,  φ(n) = (p−1)(q−1)
  public e,  private d = e⁻¹ mod φ(n)
  publishes (n, e)  ──────────────── public network ──────────────►  receives (n, e)
                                                                     C = Mᵉ mod n
  M = Cᵈ mod n  ◄─────────────────── public network ───────────────  sends C

  Eve sees n, e, and C. Recovering M needs d, which needs φ(n), which needs the factors of n.

Security. An attacker knows n, e, and C. Computing d requires φ(n), and knowing φ(n) is equivalent to factoring n (Euler's totient function, above). The best known classical factoring algorithm, the general number field sieve, takes super-polynomial time, and 2048-bit moduli are far beyond its reach. Shor's algorithm would factor efficiently on a large quantum computer, which is why post-quantum schemes are being deployed.

Signatures reverse the roles. The owner computes S = Mᵈ mod n, and anyone can verify Sᵉ ≡ M (mod n) using the public key.

Toy example. Take p = 61 and q = 53. Then n = 3233, φ(n) = 3120, e = 17, and d = 2753. Check: 17·2753 = 46801 = 15·3120 + 1.

from math import gcd

p, q = 61, 53                                      # toy primes; real ones have about 1024 bits each
n, phi_n = p * q, (p - 1) * (q - 1)                # 3233, 3120
e = 17
assert gcd(e, phi_n) == 1                          # e must be invertible modulo φ(n)
d = pow(e, -1, phi_n)                              # extended Euclid under the hood
print(n, phi_n, d)                                 # 3233 3120 2753

M = 65
C = pow(M, e, n)                                   # encrypt with the public key (n, e)
print(C, pow(C, d, n))                             # 2790 65   decrypt with the private key d

S = pow(M, d, n)                                   # sign with the private key
print(pow(S, e, n) == M)                           # True: anyone can verify with (n, e)

# CRT decryption (4.3): two half-size exponentiations instead of one full-size one
dp, dq, q_inv = d % (p - 1), d % (q - 1), pow(q, -1, p)
m1, m2 = pow(C, dp, p), pow(C, dq, q)              # M mod p and M mod q, with exponents shrunk by Fermat
h = q_inv * (m1 - m2) % p
print(m2 + h * q)                                  # 65   recombined: ≡ m1 (mod p) and ≡ m2 (mod q)

Textbook RSA is not secure as written. Real systems never encrypt Mᵉ mod n directly:

Pitfall	What goes wrong	Mitigation
Deterministic encryption	The same M always gives the same C, so an attacker can encrypt guesses ("yes", "no") and compare	Randomized padding (OAEP)
Small e and small M	If Mᵉ < n, then C = Mᵉ exactly, with no wrap-around, and an ordinary e-th root recovers M	Padding
Shared or weak primes	If two moduli share a prime, gcd(n₁, n₂) reveals it and breaks both keys	Good randomness during key generation
p and q too close	Fermat's factorization method finds them quickly	Choose the primes independently
Timing differences	Branches in square-and-multiply leak the bits of d	Constant-time implementations
Home-made implementations	Any of the problems above	Use a vetted cryptography library

Key takeaways

• Key generation: n = pq, e coprime to φ(n), and d = e⁻¹ mod φ(n) from the extended Euclidean algorithm.
• Encryption is C = Mᵉ mod n and decryption is M = Cᵈ mod n. Correctness follows from Euler's theorem and the CRT.
• Security rests on the hardness of factoring. Computing φ(n) or d from (n, e) is as hard as factoring n.
• Real deployments add randomized padding and use constant-time library code. Textbook RSA is insecure.

Practice

1. (Beginner) With p = 5, q = 11, and e = 3, compute n, φ(n), and d. Encrypt M = 9, then decrypt the result to check.
2. (Intermediate) Explain why e must satisfy gcd(e, φ(n)) = 1, and what fails for e = 2. Then show that if two RSA moduli share a prime factor, a single gcd computation breaks both keys.
3. (Interview) An attacker intercepts a yes/no vote encrypted with textbook RSA under a known public key. How can they read the vote without factoring n, and what does OAEP padding change? Hint: textbook encryption is deterministic, and the public key lets anyone encrypt.

<a id="5-combinatorics"></a>