Number Theory

How to read this page: This article maps the topic from beginner to expert across six levels � Remembering, Understanding, Applying, Analyzing, Evaluating, and Creating. Scan the headings to see the full scope, then read from wherever your knowledge starts to feel uncertain. Learn more about how BloomWiki works ?

Number theory is the branch of pure mathematics devoted to the study of integers — the whole numbers and their properties. It is one of the oldest and most beautiful areas of mathematics, stretching from Euclid's proof that there are infinitely many primes to Andrew Wiles' proof of Fermat's Last Theorem in 1995. Number theory is simultaneously elementary (anyone can understand its questions) and profound (some of its problems have resisted centuries of attack). Its central objects — prime numbers, divisibility, congruences, Diophantine equations — appear everywhere in mathematics, and have become the foundation of modern cryptography. Number theory is often called the "queen of mathematics" (Gauss), and its problems combine beauty with extraordinary depth.

Remembering

• Integer — A whole number: ..., −3, −2, −1, 0, 1, 2, 3, ... The central objects of number theory.
• Divisibility — a divides b (written a | b) if there exists an integer k such that b = ak.
• Prime number — An integer p > 1 whose only positive divisors are 1 and p itself.
• Composite number — An integer > 1 that is not prime; has at least one factor other than 1 and itself.
• Fundamental Theorem of Arithmetic — Every integer > 1 has a unique factorization into prime numbers.
• Greatest Common Divisor (GCD) — The largest positive integer dividing both a and b; computed by the Euclidean algorithm.
• Euclidean Algorithm — An ancient algorithm computing GCD(a,b) by repeated division: GCD(a,b) = GCD(b, a mod b).
• Modular arithmetic — Arithmetic "clock arithmetic"; a ≡ b (mod n) means n | (a − b).
• Congruence — a ≡ b (mod n): a and b leave the same remainder when divided by n.
• Fermat's Little Theorem — If p is prime and p ∤ a, then a^(p−1) ≡ 1 (mod p); foundation of RSA.
• Euler's Theorem — Generalization: a^φ(n) ≡ 1 (mod n) when gcd(a,n)=1; φ is Euler's totient function.
• Diophantine equation — A polynomial equation where only integer solutions are sought.
• Fermat's Last Theorem — No integer solutions to x^n + y^n = z^n for n > 2; proved by Wiles 1995.
• Goldbach's Conjecture — Every even integer > 2 is the sum of two primes; unproven since 1742.
• Riemann Hypothesis — All non-trivial zeros of the Riemann zeta function have real part 1/2; most important unsolved problem in mathematics.

Understanding

Number theory operates at several levels, from elementary divisibility to deep analytic and algebraic methods:

Primality and its mysteries: The primes are the atoms of the integers — every integer factors uniquely into primes. Yet the primes themselves resist simple description. Euclid proved there are infinitely many (classic proof: assume finitely many; multiply them all together and add 1; the result has a prime factor not in the list — contradiction). But the distribution of primes is irregular: the Prime Number Theorem (proved 1896) states that the number of primes ≤ n is approximately n/ln(n). The Riemann Hypothesis gives a more precise description of this distribution.

Modular arithmetic and its power: Modular arithmetic structures integer arithmetic by focusing on remainders. Chinese Remainder Theorem (CRT): if m₁, m₂, ... are pairwise coprime, the system x ≡ aᵢ (mod mᵢ) has a unique solution mod m₁m₂.... Fermat's Little Theorem (a^(p-1) ≡ 1 mod p for prime p) is central to primality testing and RSA encryption. Quadratic residues (which numbers are perfect squares mod p?) lead to the law of quadratic reciprocity — one of Gauss's crowning achievements.

Diophantine equations: The quest for integer solutions to polynomial equations. Pythagorean triples (x² + y² = z²) have infinitely many solutions (3,4,5), (5,12,13), etc., parameterized by Euclid's formula. Pell's equation (x² − Dy² = 1) has infinitely many solutions for non-square D. Fermat's Last Theorem (x^n + y^n = z^n, n > 2) has no solutions — Wiles' proof involved deep connections to elliptic curves and modular forms.

Connections to cryptography: Modern public-key cryptography (RSA, Diffie-Hellman, elliptic curve cryptography) is built entirely on number-theoretic foundations. RSA security rests on the apparent computational hardness of factoring large integers — despite anyone being able to multiply them together easily. This asymmetry between easy multiplication and hard factoring is a fundamental number-theoretic phenomenon.

Applying

Number theory in cryptographic applications: <syntaxhighlight lang="python"> import math import random from functools import reduce

1. === Core Number Theory ===

def gcd(a: int, b: int) -> int:

   """Euclidean algorithm — O(log min(a,b))."""
   while b:
       a, b = b, a % b
   return a

def extended_gcd(a: int, b: int) -> tuple[int, int, int]:

   """Extended Euclidean: returns (gcd, x, y) where ax + by = gcd(a,b)."""
   if a == 0:
       return b, 0, 1
   g, x, y = extended_gcd(b % a, a)
   return g, y - (b // a) * x, x

def mod_inverse(a: int, n: int) -> int:

   """Modular inverse of a mod n (requires gcd(a,n) = 1)."""
   g, x, _ = extended_gcd(a % n, n)
   if g != 1:
       raise ValueError(f"Inverse doesn't exist: gcd({a},{n}) = {g}")
   return x % n

def power_mod(base: int, exp: int, mod: int) -> int:

   """Fast modular exponentiation: base^exp mod mod — O(log exp)."""
   result = 1
   base %= mod
   while exp > 0:
       if exp & 1:
           result = result * base % mod
       base = base * base % mod
       exp >>= 1
   return result

def euler_totient(n: int) -> int:

   """Euler's totient φ(n) — count of integers coprime to n in [1,n]."""
   result = n
   p = 2
   temp = n
   while p * p <= temp:
       if temp % p == 0:
           while temp % p == 0:
               temp //= p
           result -= result // p
       p += 1
   if temp > 1:
       result -= result // temp
   return result

1. === Primality Testing ===

def miller_rabin(n: int, k: int = 10) -> bool:

   """Probabilistic primality test. Returns True if n is probably prime."""
   if n < 2: return False
   if n == 2 or n == 3: return True
   if n % 2 == 0: return False
   # Write n-1 as 2^r * d
   r, d = 0, n - 1
   while d % 2 == 0:
       r += 1; d //= 2
   for _ in range(k):
       a = random.randrange(2, n - 1)
       x = power_mod(a, d, n)
       if x == 1 or x == n - 1: continue
       for _ in range(r - 1):
           x = power_mod(x, 2, n)
           if x == n - 1: break
       else:
           return False
   return True  # Probably prime (error probability < 4^{-k})

1. === RSA Key Generation (educational) ===

def generate_rsa_keys(bits: int = 512):

   """Generate RSA public/private key pair."""
   # In practice, use cryptography library. This is for education only.
   from sympy import randprime  # For proper prime generation
   p = randprime(2_'(bits//2-1), 2_'(bits//2))
   q = randprime(2_'(bits//2-1), 2_'(bits//2))
   n = p * q          # Public modulus
   phi = (p-1)*(q-1)  # Euler's totient
   e = 65537          # Standard public exponent
   d = mod_inverse(e, phi)  # Private exponent: ed ≡ 1 (mod φ(n))
   return (n, e), (n, d)    # (public_key, private_key)

public_key, private_key = generate_rsa_keys(512) n, e = public_key

1. Encrypt: ciphertext = message^e mod n

message = 42 ciphertext = power_mod(message, e, n)

1. Decrypt: plaintext = ciphertext^d mod n

decrypted = power_mod(ciphertext, private_key[1], n) print(f"Original: {message} → Encrypted → Decrypted: {decrypted}") assert message == decrypted </syntaxhighlight>

Key results and open problems

Proved → Infinitely many primes (Euclid) · Prime Number Theorem (1896) · Fermat's Last Theorem (Wiles, 1995) · 4-Color Theorem (1976) · Poincaré Conjecture (Perelman, 2003)

Open → Riemann Hypothesis · Goldbach's Conjecture · Twin Prime Conjecture · abc Conjecture · P vs NP (related to integer factoring)

Analyzing

Important Number Theory Results

Result	Statement	Significance
Infinitely many primes	No largest prime	Proved by Euclid c.300 BCE; multiple proofs
Fermat's Little Theorem	a^p ≡ a (mod p)	Foundation of RSA, primality tests
Quadratic Reciprocity	Law governing ±1 residuosity	Gauss's "gem"; proved ~8 ways
Prime Number Theorem	π(n) ~ n/ln(n)	Proved 1896; Riemann Hypothesis refines it
Fermat's Last Theorem	No x^n+y^n=z^n (n>2)	358 years to prove; used elliptic curves

Famous open problems: Riemann Hypothesis (1859): all non-trivial zeros of ζ(s) have Re(s) = 1/2 — implies the most precise distribution of primes. Goldbach's Conjecture: every even number > 2 is the sum of two primes — verified to 4×10¹⁸, unproven. Twin Prime Conjecture: infinitely many pairs of primes differing by 2 — Zhang (2013) proved bounded gaps. Collatz Conjecture: starting from any positive integer, repeatedly dividing even numbers by 2 and multiplying odd numbers by 3+1 always reaches 1.

Evaluating

Number theory proofs are evaluated by: (1) Logical validity: is the argument logically correct, with no hidden assumptions? (2) Rigor: does the proof satisfy the standards of formal mathematical proof? (3) Elegance: is there a simpler proof? "Book proofs" (Erdős) — proofs that are most beautiful. (4) Generalizability: does the result apply to broader classes than originally proven? (5) Fruitfulness: does the proof method generate further results and open new research directions (as Wiles' proof did)?

Creating

Advanced research in number theory: (1) Analytic number theory: use complex analysis (Riemann zeta function) to study integer distribution. (2) Algebraic number theory: study rings of algebraic integers (Gaussian integers ℤ[i], cyclotomic fields) to prove results about ordinary integers. (3) Arithmetic geometry: elliptic curves, modular forms — the framework Wiles used. (4) Computational number theory: design and implement primality tests (AKS, Miller-Rabin), factoring algorithms (Pollard rho, quadratic sieve, general number field sieve), and their applications to cryptography. (5) Additive combinatorics: Green-Tao theorem (primes contain arbitrarily long arithmetic progressions) — synthesis of analytic and combinatorial methods.