Number Theory

Number theory studies the integers. Once called the "purest" mathematics, it now secures every HTTPS connection and UPI payment through cryptography.

#Divisibility

a divides b (written a | b) if b = a·k for some integer k. Examples: 3 | 12, 7 ∤ 12.

Division algorithm: for integers a and d > 0, there are unique q and r with a = d·q + r and 0 ≤ r < d. Here q = a div d and r = a mod d.

#Primes

A prime is an integer p > 1 whose only positive divisors are 1 and p. Every integer > 1 is either prime or composite.

Fundamental theorem of arithmetic: every integer > 1 can be written as a product of primes in exactly one way (up to order): 360 = 2³ · 3² · 5.

There are infinitely many primes (Euclid's proof is in the proofs lesson). To test n, try divisors up to √n; to list all primes up to n, use the Sieve of Eratosthenes:

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for p in range(2, int(n ** 0.5) + 1):
        if is_prime[p]:
            for multiple in range(p * p, n + 1, p):   # cross off multiples of p
                is_prime[multiple] = False
    return [i for i, ok in enumerate(is_prime) if ok]

def factorise(n):
    factors, d = {}, 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    return factors

print(sieve(60))
for n in (360, 1001, 97, 2026):
    print(n, "=", " · ".join(f"{p}^{e}" if e > 1 else str(p) for p, e in factorise(n).items()))

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
360 = 2^3 · 3^2 · 5
1001 = 7 · 11 · 13
97 = 97
2026 = 2 · 1013

#GCD and LCM

• gcd(a, b): the largest integer dividing both. gcd(84, 36) = 12.
• lcm(a, b): the smallest positive integer divisible by both. lcm(4, 6) = 12.
• gcd(a, b) · lcm(a, b) = a · b.
• a and b are coprime (relatively prime) if gcd(a, b) = 1.

Euclid's algorithm: gcd(a, b) = gcd(b, a mod b), and gcd(a, 0) = a. It takes O(log min(a, b)) steps.

Bézout's identity: there exist integers s, t with gcd(a, b) = s·a + t·b. The extended Euclidean algorithm finds them.

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

a, b = 252, 198
x, y = a, b
while y:
    print(f"gcd({x}, {y})", end=" = ")
    x, y = y, x % y
print(f"gcd({x}, 0) = {x}")
g, s, t = extended_gcd(a, b)
print(f"Bezout: {g} = {s}*{a} + {t}*{b}")
print("lcm =", a * b // g)

gcd(252, 198) = gcd(198, 54) = gcd(54, 36) = gcd(36, 18) = gcd(18, 0) = 18
Bezout: 18 = 4*252 + -5*198
lcm = 2772

#Modular arithmetic

a ≡ b (mod m) — "a is congruent to b modulo m" — means m | (a − b): a and b leave the same remainder when divided by m. Clock arithmetic is mod 12; days of the week are mod 7.

Congruences can be added and multiplied: if a ≡ b and c ≡ d (mod m), then a + c ≡ b + d and a·c ≡ b·d (mod m). So you can reduce at every step:

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

#Fast modular exponentiation

Compute aᵉ mod m by repeated squaring in O(log e) multiplications:

def mod_pow(a, e, m):
    result = 1
    a %= m
    while e > 0:
        if e & 1:                 # this bit of the exponent is set
            result = result * a % m
        a = a * a % m             # square for the next bit
        e >>= 1
    return result

print(mod_pow(3, 200, 13), pow(3, 200, 13))          # Python's pow does the same
print("last 3 digits of 7^2026:", mod_pow(7, 2026, 1000))
days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]
print("100 days after a Saturday is a", days[(days.index("Sat") + 100) % 7])

9 9
last 3 digits of 7^2026: 649
100 days after a Saturday is a Mon

#Modular inverses

The inverse of a modulo m is a number a⁻¹ with a·a⁻¹ ≡ 1 (mod m). It exists iff gcd(a, m) = 1, and the extended Euclidean algorithm finds it. Example: 3⁻¹ mod 7 = 5, since 3·5 = 15 ≡ 1.

Fermat's little theorem: if p is prime and p ∤ a, then aᵖ⁻¹ ≡ 1 (mod p). So a⁻¹ ≡ aᵖ⁻² (mod p).

#Applications

p, q = 61, 53                      # toy RSA (real keys use primes with hundreds of digits)
n, phi = p * q, (p - 1) * (q - 1)
e = 17                             # public exponent, coprime with phi
d = pow(e, -1, phi)                # private exponent: modular inverse (Python 3.8+)
message = 65
cipher = pow(message, e, n)
print(f"n={n}, e={e}, d={d}")
print(f"encrypt {message} -> {cipher}, decrypt -> {pow(cipher, d, n)}")

n=3233, e=17, d=2753
encrypt 65 -> 2790, decrypt -> 65