Number theory is the study of integers and their properties. Often called “the queen of mathematics,” it has surprising applications in cryptography and computer science.
Divisibility
Basic Definitions
- a divides b (written a | b) if b = ka for some integer k
- Properties:
- Reflexive: a | a
- Transitive: if a | b and b | c, then a | c
- If a | b and a | c, then a | (bx + cy) for any integers x, y
Division Algorithm
For any integers a, b with b > 0, there exist unique integers q (quotient) and r (remainder) such that:
a = bq + r where 0 ≤ r < b
Greatest Common Divisor (GCD)
The greatest common divisor gcd(a, b) is the largest positive integer that divides both a and b.
Properties:
- gcd(a, b) = gcd(b, a)
- gcd(a, 0) = |a|
- gcd(a, b) = gcd(b, a mod b)
Euclidean Algorithm:
gcd(a, b):
while b ≠ 0:
a, b = b, a mod b
return a
Least Common Multiple (LCM)
The least common multiple lcm(a, b) is the smallest positive integer divisible by both a and b.
Key relationship:
gcd(a, b) × lcm(a, b) = |a × b|
Bézout’s Identity
For any integers a and b, there exist integers x and y such that:
gcd(a, b) = ax + by
The Extended Euclidean Algorithm computes both gcd(a, b) and the coefficients x, y.
Prime Numbers
Fundamental Theorem of Arithmetic
Every integer greater than 1 can be expressed uniquely as a product of prime numbers (up to ordering).
For example: 360 = 2³ × 3² × 5
Properties of Primes
- There are infinitely many primes (Euclid’s proof by contradiction)
- The prime counting function π(n) counts primes ≤ n
- Prime Number Theorem: π(n) ~ n/ln(n) as n → ∞
Testing Primality
| Method | Type | Complexity |
|---|---|---|
| Trial division | Deterministic | O(√n) |
| Miller-Rabin | Probabilistic | O(k log³n) |
| AKS | Deterministic | O(log⁶n) |
Finding Primes
Sieve of Eratosthenes:
- List integers from 2 to n
- Mark 2 as prime, cross out all multiples of 2
- Find next unmarked number, mark as prime, cross out its multiples
- Repeat until √n
Sieve of Atkin: A more efficient modern sieve with complexity O(n/log log n).
Special Primes
- Mersenne primes: 2^p - 1 (e.g., 3, 7, 31, 127)
- Fermat primes: 2^(2^n) + 1 (only five known: 3, 5, 17, 257, 65537)
- Twin primes: pairs (p, p+2) where both are prime (e.g., 11 and 13)
- Sophie Germain primes: p where 2p + 1 is also prime
Modular Arithmetic
Congruences
We say a ≡ b (mod n) if n divides (a - b), i.e., a and b have the same remainder when divided by n.
Properties (congruence is an equivalence relation):
- Reflexive: a ≡ a (mod n)
- Symmetric: if a ≡ b, then b ≡ a (mod n)
- Transitive: if a ≡ b and b ≡ c, then a ≡ c (mod n)
Arithmetic:
- (a + b) mod n = ((a mod n) + (b mod n)) mod n
- (a × b) mod n = ((a mod n) × (b mod n)) mod n
Residue Systems
- Complete residue system mod n: {0, 1, 2, …, n-1}
- Reduced residue system mod n: elements coprime to n
- For n = 12: {1, 5, 7, 11}
Linear Congruences
To solve ax ≡ b (mod n):
- Solvable if and only if gcd(a, n) | b
- If solvable with d = gcd(a, n), there are exactly d solutions mod n
- Use Extended Euclidean Algorithm to find solutions
Chinese Remainder Theorem
Given a system of congruences:
- x ≡ a₁ (mod n₁)
- x ≡ a₂ (mod n₂)
- …
- x ≡ aₖ (mod nₖ)
If the moduli n₁, n₂, …, nₖ are pairwise coprime, there exists a unique solution modulo N = n₁ × n₂ × … × nₖ.
Important Theorems
Fermat’s Little Theorem
If p is prime and p does not divide a:
a^(p-1) ≡ 1 (mod p)
Equivalently: a^p ≡ a (mod p) for all integers a.
Euler’s Theorem
If gcd(a, n) = 1:
a^φ(n) ≡ 1 (mod n)
This generalises Fermat’s Little Theorem.
Euler’s Totient Function
φ(n) counts integers k where 1 ≤ k ≤ n and gcd(k, n) = 1.
Formulas:
- φ(p) = p - 1 for prime p
- φ(p^k) = p^k - p^(k-1) = p^(k-1)(p - 1)
- φ(mn) = φ(m)φ(n) if gcd(m, n) = 1 (multiplicative)
- φ(n) = n × ∏(1 - 1/p) for all prime divisors p of n
| n | φ(n) | Reduced residues |
|---|---|---|
| 6 | 2 | {1, 5} |
| 8 | 4 | {1, 3, 5, 7} |
| 12 | 4 | {1, 5, 7, 11} |
Wilson’s Theorem
An integer p > 1 is prime if and only if:
(p-1)! ≡ -1 (mod p)
Diophantine Equations
Linear Diophantine Equations
The equation ax + by = c has integer solutions if and only if gcd(a, b) | c.
If (x₀, y₀) is a particular solution, the general solution is:
- x = x₀ + (b/d)t
- y = y₀ - (a/d)t
where d = gcd(a, b) and t is any integer.
Pythagorean Triples
Integer solutions to x² + y² = z².
Primitive solutions (gcd(x, y, z) = 1) are given by:
- x = m² - n²
- y = 2mn
- z = m² + n²
where m > n > 0, gcd(m, n) = 1, and m - n is odd.
Examples: (3, 4, 5), (5, 12, 13), (8, 15, 17), (7, 24, 25)
Fermat’s Last Theorem
The equation x^n + y^n = z^n has no positive integer solutions for n > 2.
Conjectured by Pierre de Fermat in 1637, proved by Andrew Wiles in 1995 after 358 years.
Pell’s Equation
For non-square positive integer D, the equation x² - Dy² = 1 has infinitely many solutions.
The fundamental solution can be found using continued fractions.
Example: x² - 2y² = 1 has solutions (1, 0), (3, 2), (17, 12), (99, 70), …
Cryptographic Applications
RSA Algorithm
The RSA cryptosystem relies on the difficulty of factoring large numbers.
Key Generation:
- Choose large primes p and q
- Compute n = pq (modulus)
- Compute φ(n) = (p-1)(q-1)
- Choose e coprime to φ(n) (commonly e = 65537)
- Compute d ≡ e⁻¹ (mod φ(n)) using Extended Euclidean Algorithm
Keys:
- Public key: (n, e)
- Private key: d
Operations:
- Encrypt: c ≡ m^e (mod n)
- Decrypt: m ≡ c^d (mod n)
Security depends on the infeasibility of factoring n to recover p and q.
Diffie-Hellman Key Exchange
Allows two parties to establish a shared secret over an insecure channel.
Based on the discrete logarithm problem: given g^a mod p, finding a is computationally hard.
Elliptic Curve Cryptography
Uses the group structure of points on elliptic curves over finite fields.
Advantages: smaller key sizes for equivalent security compared to RSA.
Quadratic Residues
Definition
An integer a is a quadratic residue modulo n if the congruence x² ≡ a (mod n) has a solution.
For prime p, exactly (p-1)/2 of the non-zero residues are quadratic residues.
Legendre Symbol
For odd prime p and integer a not divisible by p:
(a/p) = 1 if a is a quadratic residue mod p
(a/p) = -1 if a is a quadratic non-residue mod p
Euler’s criterion: (a/p) ≡ a^((p-1)/2) (mod p)
Quadratic Reciprocity
For distinct odd primes p and q:
(p/q)(q/p) = (-1)^((p-1)/2 × (q-1)/2)
This means (p/q) = (q/p) unless both p ≡ q ≡ 3 (mod 4).
Supplementary laws:
- (-1/p) = (-1)^((p-1)/2)
- (2/p) = (-1)^((p²-1)/8)
Learning Resources
Books
- A Friendly Introduction to Number Theory by Joseph Silverman
- An Introduction to the Theory of Numbers by Hardy and Wright
- Elementary Number Theory by David Burton
- Number Theory: A Lively Introduction by James Pommersheim
Online Courses
Related Topics
- Abstract Algebra - groups, rings, and fields
- Discrete Mathematics - combinatorics and graph theory
- Mathematical Proofs - proof techniques
- Cryptography - applications of number theory