What Is Number Theory? Primes, Proofs, and Modern Cryptography

What Is Number Theory?

Number theory is the branch of mathematics concerned with the properties and relationships of integers — the counting numbers (1, 2, 3, …), their negatives, and zero. Often called the "queen of mathematics" (a phrase attributed to Carl Friedrich Gauss), number theory studies questions about divisibility, prime numbers, integer solutions to equations, and the deep structure underlying the seemingly simple sequence of whole numbers. Despite involving objects as elementary as the integers, number theory produces some of mathematics' deepest theorems and most difficult unsolved problems. Its central objects — prime numbers — underpin not only centuries of pure mathematics but also the cryptographic systems that secure virtually all modern digital communications and commerce.

Number theory divides broadly into several subfields: elementary number theory (divisibility, modular arithmetic, basic prime theory), analytic number theory (using calculus and complex analysis to study primes), algebraic number theory (extending the integers to broader algebraic structures), and computational number theory (algorithms for integer problems with direct cryptographic application).

Prime Numbers

A prime number is a natural number greater than 1 that has no positive integer divisors other than 1 and itself. The first several primes are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 … The number 2 is the only even prime; all others are odd. The Fundamental Theorem of Arithmetic (proved rigorously by Gauss in 1801) states that every integer greater than 1 can be expressed uniquely as a product of prime numbers (up to the order of factors). This makes primes the multiplicative building blocks of all integers, analogous to elements in chemistry.

Euclid proved around 300 BCE that there are infinitely many primes — one of the oldest proofs in mathematics, using an elegant argument by contradiction: assume finitely many primes p₁, p₂, …, pₙ; consider the number N = p₁ × p₂ × … × pₙ + 1; N is either prime (contradicting that all primes are in the list) or has a prime factor not in the list (also a contradiction). Therefore the list cannot be finite.

The Distribution of Primes

While primes are infinite, they become less frequent among larger numbers. The Prime Number Theorem (independently proved by Hadamard and de la Vallée Poussin in 1896) quantifies this: the number of primes up to N, denoted π(N), is approximately N / ln(N) — the natural logarithm. For example, there are 168 primes below 1,000; the approximation gives 1,000 / ln(1,000) ≈ 145. The error decreases proportionally as N grows.

The Riemann Hypothesis — formulated by Bernhard Riemann in 1859 and still unproven — states that the non-trivial zeros of the Riemann zeta function ζ(s) all lie on the line Re(s) = 1/2 in the complex plane. It is equivalent to the strongest known conjecture about the distribution of primes and is one of the seven Millennium Prize Problems, each carrying a $1,000,000 prize from the Clay Mathematics Institute.

Modular Arithmetic

Modular arithmetic — sometimes called "clock arithmetic" — is the study of remainders after division. We say a ≡ b (mod n) if n divides (a – b). The integers modulo n form a finite system with only n elements {0, 1, 2, …, n–1}, within which addition, subtraction, and multiplication are well-defined. Modular arithmetic is foundational to number theory and to cryptographic algorithms.

Key results in modular arithmetic include:

• Fermat's Little Theorem: If p is prime and a is not divisible by p, then a^(p–1) ≡ 1 (mod p). This is a cornerstone of primality testing and the RSA algorithm.
• Euler's Theorem: Generalizes Fermat's Little Theorem: a^φ(n) ≡ 1 (mod n) whenever gcd(a, n) = 1, where φ(n) is Euler's totient function (the count of integers 1–n coprime to n).
• Chinese Remainder Theorem: If n₁, n₂, …, nₖ are pairwise coprime, then any system of simultaneous congruences x ≡ aᵢ (mod nᵢ) has a unique solution modulo n₁n₂…nₖ. Used in both pure number theory and practical algorithm design.

Fermat's Last Theorem

Pierre de Fermat wrote in the margin of his copy of Diophantus's Arithmetica (circa 1637): "It is impossible to write a cube as the sum of two cubes, a fourth power as the sum of two fourth powers, and in general any power greater than the second as the sum of two like powers" — adding that he had "discovered a truly marvelous proof of this, which this margin is too narrow to contain." The formal statement: there are no positive integers x, y, z satisfying xⁿ + yⁿ = zⁿ for any integer n > 2.

The theorem resisted proof for 358 years. It was finally proved by British mathematician Andrew Wiles in 1995 (with a crucial repair by Wiles and Richard Taylor), using techniques from algebraic geometry and the theory of elliptic curves — fields that did not exist in Fermat's era. The proof runs to over 100 pages and connects Fermat's elementary statement to deep results in modern mathematics (the Taniyama–Shimura conjecture, now the modularity theorem). Wiles received the Abel Prize in 2016 for this achievement.

Number Theory and Cryptography

The most direct modern application of number theory is public-key cryptography — the mathematical foundation of secure internet communications, digital signatures, online banking, and encrypted messaging. Every HTTPS connection (the padlock in a browser) relies on number-theoretic hardness assumptions.

The RSA Cryptosystem

RSA (Rivest, Shamir, Adleman, 1977) is based on the computational difficulty of integer factorization: multiplying two large primes is fast, but recovering the primes from their product is believed to be computationally infeasible for sufficiently large numbers.

Modern RSA key sizes are typically 2,048–4,096 bits. Factoring a 2,048-bit number would require computational resources far beyond current technology using classical algorithms (the best known, the General Number Field Sieve, has sub-exponential but still enormous complexity). However, a sufficiently large quantum computer running Shor's algorithm — a quantum algorithm published by Peter Shor in 1994 — could factor such numbers in polynomial time, potentially breaking RSA. This has prompted work on post-quantum cryptography — cryptographic systems based on mathematical problems believed to be hard even for quantum computers, including lattice problems and hash-based signatures.

Unsolved Problems

Number theory contains more famous unsolved problems than perhaps any other mathematical field:

• Goldbach's Conjecture (1742): Every even integer greater than 2 is the sum of two primes. Verified computationally for all even numbers up to 4 × 10¹⁸; no proof exists.
• Twin Prime Conjecture: There are infinitely many pairs of primes differing by 2 (e.g., 11 and 13; 17 and 19). A landmark 2013 result by Yitang Zhang proved infinitely many prime pairs within a finite gap (initially 70,000,000; reduced to 246 by the Polymath project).
• Riemann Hypothesis: The non-trivial zeros of the Riemann zeta function all lie on Re(s) = 1/2 — a Millennium Prize Problem.
• Collatz Conjecture: Starting from any positive integer, repeatedly applying the rule (if even, divide by 2; if odd, multiply by 3 and add 1) always eventually reaches 1. Verified for all starting values below 2⁶⁸; no proof exists.