Number Theory Basics

Number theory studies the properties of integers. It is the foundation of modern cryptography and appears throughout algorithm design.

Divisibility

Definition: For integers a, b with a ≠ 0, we say a divides b (written a | b) if there exists an integer k such that b = ak.

3 | 12    (12 = 3 × 4)     ✓
5 | 17    (17/5 is not an integer)  ✗
7 | 0     (0 = 7 × 0)      ✓

Properties:

a | 0 for all a ≠ 0
1 | a for all a
If a | b and a | c, then a | (b + c) and a | (b - c)
If a | b and b | c, then a | c (transitivity)
If a | b and a | c, then a | (mb + nc) for any integers m, n (linear combination)
If a | b and b ≠ 0, then |a| ≤ |b|

Division Algorithm

Theorem: For any integers a and d with d > 0, there exist unique integers q (quotient) and r (remainder) such that:

a = dq + r,    0 ≤ r < d

Example: a = 17, d = 5: 17 = 5(3) + 2, so q = 3, r = 2.

Example: a = -11, d = 3: -11 = 3(-4) + 1, so q = -4, r = 1.

Note: In programming, the % operator may not match this definition for negative numbers. In Rust, -11 % 3 = -2 (truncated division). Use .rem_euclid() for the mathematical definition.

Greatest Common Divisor (GCD)

The GCD of integers a and b (not both zero) is the largest integer that divides both.

gcd(a, b) = max{d ∈ ℤ⁺ | d | a ∧ d | b}

Properties:

gcd(a, 0) = |a|
gcd(a, b) = gcd(b, a)
gcd(a, b) = gcd(|a|, |b|)
gcd(a, b) = gcd(a, b - a) (if b > a)
a and b are coprime (relatively prime) if gcd(a, b) = 1

Finding GCD by prime factorization: If a = p₁^α₁ · p₂^α₂ · ... and b = p₁^β₁ · p₂^β₂ · ..., then:

gcd(a, b) = p₁^min(α₁,β₁) · p₂^min(α₂,β₂) · ...

Example: gcd(72, 120)

72 = 2³ · 3²
120 = 2³ · 3 · 5
gcd = 2³ · 3¹ = 24

Euclidean Algorithm

An efficient method to compute GCD without factoring.

Algorithm: Repeatedly apply the division algorithm:

gcd(a, b) = gcd(b, a mod b)

until the remainder is 0. The last non-zero remainder is the GCD.

Example: gcd(252, 198)

252 = 198(1) + 54      gcd(252, 198) = gcd(198, 54)
198 = 54(3) + 36       gcd(198, 54)  = gcd(54, 36)
54  = 36(1) + 18       gcd(54, 36)   = gcd(36, 18)
36  = 18(2) + 0        gcd(36, 18)   = 18

So gcd(252, 198) = 18.

Correctness: Based on the fact that gcd(a, b) = gcd(b, a mod b).

Proof: Let d = gcd(a, b). Then d | a and d | b. Since a mod b = a - b⌊a/b⌋, d | (a mod b). So d divides both b and a mod b, meaning d ≤ gcd(b, a mod b). The reverse inequality follows similarly.

Time complexity: O(log(min(a, b))) divisions. This is because the remainder decreases by at least half every two steps (related to the Fibonacci numbers — the worst case input is consecutive Fibonacci numbers).

Extended Euclidean Algorithm

Finds integers x, y such that:

ax + by = gcd(a, b)

This is called Bézout's identity: For any integers a, b, there exist integers x, y such that ax + by = gcd(a, b).

Algorithm: Work backward through the Euclidean algorithm steps.

Example: Find x, y such that 252x + 198y = gcd(252, 198) = 18.

From the Euclidean algorithm:

18 = 54 - 36(1)
36 = 198 - 54(3)
54 = 252 - 198(1)

Substituting backward:

18 = 54 - 36(1)
   = 54 - (198 - 54(3))(1)
   = 54(4) - 198(1)
   = (252 - 198(1))(4) - 198(1)
   = 252(4) + 198(-5)

So x = 4, y = -5. Verify: 252(4) + 198(-5) = 1008 - 990 = 18. ✓

Application: Finding modular inverses (see below).

FUNCTION EXTENDED_GCD(a, b)
    IF b = 0 THEN
        RETURN (a, 1, 0)
    ELSE
        (g, x, y) ← EXTENDED_GCD(b, a MOD b)
        RETURN (g, y, x - (a / b) * y)

Least Common Multiple (LCM)

The LCM of a and b is the smallest positive integer divisible by both.

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

Using prime factorization:

lcm(a, b) = p₁^max(α₁,β₁) · p₂^max(α₂,β₂) · ...

Example: lcm(12, 18) = 12 × 18 / gcd(12, 18) = 216 / 6 = 36.

Key identity: gcd(a, b) × lcm(a, b) = |a × b|.

Prime Numbers

A prime number p > 1 has no positive divisors other than 1 and p.

A composite number n > 1 has a divisor d with 1 < d < n.

The number 1 is neither prime nor composite.

First primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, ...

Infinitude of primes: There are infinitely many primes (Euclid's proof — see proof techniques).

Fundamental Theorem of Arithmetic

Every integer n > 1 can be uniquely represented as a product of primes (up to ordering).

n = p₁^α₁ · p₂^α₂ · ... · pₖ^αₖ

where p₁ < p₂ < ... < pₖ are primes and αᵢ ≥ 1.

Example: 360 = 2³ · 3² · 5.

Proof sketch:

Existence: By strong induction (proved in proof techniques topic).
Uniqueness: Requires Euclid's lemma: if p | ab, then p | a or p | b.

Testing for Primality

Trial division: Check if any integer from 2 to √n divides n.

Why √n? If n = ab with a ≤ b, then a ≤ √n.

FUNCTION IS_PRIME(n)
    IF n < 2 THEN RETURN false
    IF n < 4 THEN RETURN true
    IF n MOD 2 = 0 OR n MOD 3 = 0 THEN RETURN false
    i ← 5
    WHILE i * i ≤ n DO
        IF n MOD i = 0 OR n MOD (i + 2) = 0 THEN RETURN false
        i ← i + 6
    RETURN true

Time: O(√n). For large numbers, use Miller-Rabin (covered in algorithms).

Sieve of Eratosthenes

Finds all primes up to n in O(n log log n) time.

FUNCTION SIEVE(n)
    is_prime ← array of (n + 1) values, all set to true
    is_prime[0] ← false
    IF n > 0 THEN is_prime[1] ← false
    i ← 2
    WHILE i * i ≤ n DO
        IF is_prime[i] THEN
            j ← i * i
            WHILE j ≤ n DO
                is_prime[j] ← false
                j ← j + i
        i ← i + 1
    RETURN is_prime

Prime Number Theorem

The number of primes up to n, denoted π(n), satisfies:

π(n) ~ n / ln(n)     as n → ∞

This means the "density" of primes near n is about 1/ln(n). A random number near n has about a 1/ln(n) chance of being prime.

Modular Arithmetic

Congruences

Definition: a ≡ b (mod m) if m | (a - b).

Equivalently: a and b have the same remainder when divided by m.

17 ≡ 5 (mod 12)    (17 - 5 = 12, and 12 | 12)
-3 ≡ 4 (mod 7)     (-3 - 4 = -7, and 7 | -7)

Properties (if a ≡ b (mod m) and c ≡ d (mod m)):

a + c ≡ b + d (mod m)
a - c ≡ b - d (mod m)
a × c ≡ b × d (mod m)
aⁿ ≡ bⁿ (mod m) for n ≥ 0

Warning: Division does not always work! a/c ≡ b/d (mod m) is not generally valid.

The ℤₘ Ring

The integers modulo m form a ring: ℤₘ = {0, 1, 2, ..., m-1} with addition and multiplication modulo m.

In ℤ₇: 5 + 4 = 2,  3 × 4 = 5,  6 + 1 = 0

Modular Inverse

The modular inverse of a modulo m is an integer a⁻¹ such that:

a · a⁻¹ ≡ 1 (mod m)

Existence: a⁻¹ exists if and only if gcd(a, m) = 1 (a and m are coprime).

Finding the inverse: Use the extended Euclidean algorithm. If ax + my = 1, then x ≡ a⁻¹ (mod m).

Example: Find 3⁻¹ (mod 7). Extended GCD: 3(5) + 7(-2) = 1, so 3⁻¹ ≡ 5 (mod 7). Verify: 3 × 5 = 15 ≡ 1 (mod 7). ✓

Fermat's Little Theorem

If p is prime and gcd(a, p) = 1, then:

a^(p-1) ≡ 1 (mod p)

Equivalently: a^p ≡ a (mod p) for all integers a.

Example: 2^6 = 64 ≡ 1 (mod 7). ✓

Application: Fast modular inverse. Since a^(p-1) ≡ 1 (mod p), we have a⁻¹ ≡ a^(p-2) (mod p).

Application: Fast modular exponentiation via exponentiation by squaring.

Euler's Theorem

Generalizes Fermat's little theorem to non-prime moduli.

Euler's Totient Function φ(n)

φ(n) = count of integers in {1, 2, ..., n} that are coprime to n.

Formula for prime powers: φ(pᵏ) = pᵏ - pᵏ⁻¹ = pᵏ(1 - 1/p).

Formula for general n: If n = p₁^α₁ · p₂^α₂ · ... · pₖ^αₖ, then:

φ(n) = n · (1 - 1/p₁) · (1 - 1/p₂) · ... · (1 - 1/pₖ)

Examples:

φ(1) = 1
φ(p) = p - 1 for prime p
φ(12) = 12 · (1 - 1/2) · (1 - 1/3) = 12 · 1/2 · 2/3 = 4 (The integers coprime to 12 in {1,...,12}: {1, 5, 7, 11})

Euler's Theorem: If gcd(a, n) = 1, then:

a^φ(n) ≡ 1 (mod n)

This reduces to Fermat's little theorem when n is prime (since φ(p) = p - 1).

Chinese Remainder Theorem (CRT)

If m₁, m₂, ..., mₖ are pairwise coprime (gcd(mᵢ, mⱼ) = 1 for i ≠ j), then the system:

x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
  ⋮
x ≡ aₖ (mod mₖ)

has a unique solution modulo M = m₁ · m₂ · ... · mₖ.

Constructive Proof

Let Mᵢ = M / mᵢ. Since gcd(Mᵢ, mᵢ) = 1, there exists yᵢ with Mᵢ · yᵢ ≡ 1 (mod mᵢ).

Then:

x = Σ aᵢ · Mᵢ · yᵢ (mod M)

Example: Solve x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7).

M = 3 × 5 × 7 = 105.

M₁ = 35, 35 · y₁ ≡ 1 (mod 3), 35 ≡ 2 (mod 3), 2 · 2 = 4 ≡ 1, so y₁ = 2.
M₂ = 21, 21 · y₂ ≡ 1 (mod 5), 21 ≡ 1 (mod 5), so y₂ = 1.
M₃ = 15, 15 · y₃ ≡ 1 (mod 7), 15 ≡ 1 (mod 7), so y₃ = 1.

x = 2(35)(2) + 3(21)(1) + 2(15)(1) = 140 + 63 + 30 = 233 ≡ 23 (mod 105).

Verify: 23 mod 3 = 2 ✓, 23 mod 5 = 3 ✓, 23 mod 7 = 2 ✓.

Applications:

RSA decryption speedup (decrypt mod p and mod q separately, combine with CRT).
Fast large-number arithmetic (represent number by residues mod several primes).
Scheduling problems.

Modular Exponentiation

Computing a^n mod m efficiently using exponentiation by squaring (binary method).

Idea: Write n in binary and repeatedly square.

a^13 mod m:
13 = 1101₂ = 8 + 4 + 1
a^13 = a^8 · a^4 · a^1

Compute a, a², a⁴, a⁸ by successive squaring (mod m at each step).

FUNCTION MOD_POW(base, exp, modulus)
    result ← 1
    base ← base MOD modulus
    WHILE exp > 0 DO
        IF exp MOD 2 = 1 THEN
            result ← (result * base) MOD modulus
        exp ← exp / 2  (integer division)
        base ← (base * base) MOD modulus
    RETURN result

Time: O(log n) multiplications.

Real-World Applications

RSA cryptography: Based on the difficulty of factoring large numbers. Uses Euler's theorem for decryption: m^(ed) ≡ m (mod n) where ed ≡ 1 (mod φ(n)).
Hashing: Many hash functions use modular arithmetic (h(k) = k mod m).
Checksums: ISBN, credit card numbers (Luhn algorithm), and other validation codes use modular arithmetic.
Random number generation: Linear congruential generators use the recurrence x_{n+1} = (ax_n + c) mod m.
Computer clocks: Wrap-around arithmetic (e.g., 32-bit timestamps) is modular arithmetic.
Error-correcting codes: Reed-Solomon codes work over finite fields (ℤₚ and extensions), using polynomial arithmetic modulo irreducible polynomials.
Competitive programming: Results "modulo 10⁹ + 7" use all the properties above — modular inverse, fast exponentiation, CRT.