Number Theory & Modular Arithmetic

Modular arithmetic — 'clock arithmetic' — is the foundation of cryptography, hashing, checksums and error-detecting codes. Learn divisibility, primes, gcd and the Euclidean algorithm, Bézout's identity, congruences, modular inverses, fast modular exponentiation, Fermat's and Euler's theorems, and the Chinese Remainder Theorem.

On a 12-hour clock, 9 + 5 = 2. Mathematicians write 14 ≡ 2 (mod 12). Working 'mod n' keeps numbers bounded while preserving addition and multiplication — perfect for computers with fixed-size registers.

The security of HTTPS, banking cards and software updates rests on facts about primes and modular powers: easy to compute one way, practically impossible to reverse without a secret.

An analogy

Modular arithmetic is a number line wrapped around a circle of circumference n. However far you walk, only your position on the circle matters.

Remainders and congruences

a mod n is the remainder after dividing by n. Congruences behave like equations for + and ×: if a ≡ b and c ≡ d (mod n) then a + c ≡ b + d and ac ≡ bd. So you can reduce at every step — (123 × 456) mod 7 = (4 × 1) mod 7 = 4.

Division is the tricky one: it only works when the divisor has an inverse, i.e. is coprime to n.

Euclid and inverses

The Euclidean algorithm finds gcd in O(log n) steps by repeated remainders. Running it 'backwards' (extended Euclid) produces Bézout coefficients; if gcd(a, n) = 1, the coefficient of a is its modular inverse — the key step in RSA key generation.

Fast modular exponentiation

Compute a^e mod n by squaring repeatedly and multiplying for each 1-bit of e: about 2·log₂e multiplications. Fermat's theorem shortens exponents: 3^200 mod 13 → 3^(200 mod 12) = 3⁸ ≡ 9.

Why it is hard to reverse

Multiplying two 1024-bit primes is instant; factoring their product is beyond all classical computers. Computing gᵏ mod p is fast; recovering k (the discrete logarithm) is infeasible for large p. These one-way functions with trapdoors underlie public-key cryptography. Shor's quantum algorithm would break both, motivating post-quantum (lattice-based) schemes.

Formulas

Worked example: Modular inverse

Given: 7⁻¹ mod 40

Find: x with 7x ≡ 1 (mod 40).

Answer: 7⁻¹ ≡ 23 (7·23 = 161 = 4·40 + 1)

Worked example: Large power

Given: 3²⁰⁰ mod 13

Find: Value.

Answer: 9

Worked example: Chinese Remainder Theorem

Given: x ≡ 2 (mod 3), 3 (mod 5), 2 (mod 7)

Find: Smallest x.

Answer: x = 23

Extended Euclid, inverses, fast powers and CRT

def egcd(a, b):
    """Extended Euclid: returns (g, x, y) with a*x + b*y = g = gcd(a, b)."""
    if b == 0:
        return a, 1, 0
    g, x, y = egcd(b, a % b)
    return g, y, x - (a // b) * y

print("gcd(240, 46) and Bezout:", egcd(240, 46))
g, x, _ = egcd(7, 40)
print("inverse of 7 mod 40 =", x % 40, " check:", (7 * (x % 40)) % 40)
print("3^200 mod 13 =", pow(3, 200, 13))
# Chinese remainder: x = 2 (mod 3), 3 (mod 5), 2 (mod 7)
M = 3 * 5 * 7
x = sum(r * (M // m) * pow(M // m, -1, m) for r, m in [(2, 3), (3, 5), (2, 7)]) % M
print("CRT solution x =", x)
# gcd(240, 46) and Bezout: (2, -9, 47)
# inverse of 7 mod 40 = 23  check: 1
# 3^200 mod 13 = 9
# CRT solution x = 23

240·(−9) + 46·47 = 2 verifies Bézout. pow(a, e, n) uses square-and-multiply, so even 2048-bit exponents take milliseconds.

Common mistakes

Applications

Key takeaways

Going further