Number Theory

A prime number is a natural number greater than 1 whose only positive divisors are 1 and itself — it cannot be written as a product of two smaller natural numbers. 2, 3, 5, 7, 11, 13, … are prime; numbers like 4, 6, 9 that do factor are called composite. Primes are the multiplicative 'atoms' of arithmetic: every whole number greater than 1 is a prime or a unique product of primes. There are infinitely many of them, a fact known since Euclid.

A divisor of an integer n is an integer d that can be multiplied by some integer to produce n; equivalently, n is a multiple of d. An integer n is divisible (or evenly divisible) by d if d is a divisor of n — meaning n divided by d leaves no remainder. For example, 7 is a divisor of 42 because 7 × 6 = 42, so 42 is divisible by 7. Divisibility is the most basic relation in number theory, underlying primes, factorization, the Euclidean algorithm, and modular arithmetic.

The greatest common divisor (GCD), also called the greatest common factor (GCF), of two or more integers not all zero is the largest positive integer that divides each of them. For two integers x and y, the greatest common divisor is denoted gcd(x, y); for example, gcd(8, 12) = 4. The least common multiple (LCM) is the smallest positive integer that is a multiple of each of the given integers, e.g. lcm(4, 6) = 12. GCD and LCM are dual notions connected by the identity gcd(a,b)·lcm(a,b) = a·b, and both are computed efficiently via the Euclidean algorithm.

The Euclidean algorithm is one of the oldest algorithms still in use — it appears in Euclid's Elements (c. 300 BCE) — and computes the greatest common divisor (GCD) of two integers without factoring either of them. Its engine is a single fact: any common divisor of a and b also divides their difference, and more sharply, gcd(a, b) = gcd(b, a mod b). Repeatedly replacing the larger number by the remainder of dividing it by the smaller shrinks the pair quickly; when the remainder hits 0, the last nonzero remainder is the GCD. Because the numbers fall at least geometrically, the algorithm runs in O(log(min(a, b))) division steps — dramatically faster than listing divisors or factoring, which is why it underlies modular inverses, RSA key setup, and continued fractions.

Fermat's little theorem (stated by Pierre de Fermat in 1640) says that raising any integer to a prime power leaves the number unchanged modulo that prime: aᵖ ≡ a (mod p) for every prime p. When a is not a multiple of p, dividing through by a gives the sharper and more useful form aᵖ⁻¹ ≡ 1 (mod p). This is the reason modular exponentiation is so tame for prime moduli — the exponent only matters modulo p − 1 — and it powers the Fermat primality test, the correctness of RSA decryption, and fast computation of modular inverses (since a·aᵖ⁻² ≡ 1). It is the p-prime special case of Euler's theorem.

Euler's totient function φ(n) counts how many integers from 1 to n are coprime to n (share no common factor with it beyond 1). For a prime p every one of 1, …, p − 1 qualifies, so φ(p) = p − 1; for composite n fewer do, e.g. φ(12) = 4 (only 1, 5, 7, 11). The function is multiplicative — φ(mn) = φ(m)φ(n) when gcd(m, n) = 1 — which together with φ(pᵏ) = pᵏ − pᵏ⁻¹ lets you compute it straight from a prime factorization. Its importance comes from Euler's theorem, a^φ(n) ≡ 1 (mod n) for gcd(a, n) = 1, which generalizes Fermat's little theorem to any modulus and is the exact fact that makes RSA encryption invertible.

A Diophantine equation is a polynomial equation, named after the 3rd-century Alexandrian mathematician Diophantus, for which only integer (or sometimes rational) solutions are sought. The simplest and most important family is the linear Diophantine equation ax + by = c in two unknowns: a complete theory tells you exactly when solutions exist and how to list all of them, using nothing more than the Euclidean algorithm. By Bézout's identity, gcd(a, b) always divides ax + by for any integers x, y, so ax + by = c has an integer solution precisely when gcd(a, b) divides c — and if one solution is found, every other solution is obtained by shifting x and y by multiples of b/gcd(a,b) and a/gcd(a,b) respectively. Beyond the linear case, Diophantine equations range from the tractable (Pythagorean triples x² + y² = z²) to the notoriously hard (Fermat's Last Theorem xⁿ + yⁿ = zⁿ, unsolved for over 350 years) and even the undecidable (Hilbert's tenth problem showed no general algorithm can decide solvability).

The Chinese remainder theorem (CRT), first recorded by the mathematician Sunzi in the 3rd–5th century CE and generalized in the West by Gauss, says that a system of congruences with pairwise coprime moduli always has a unique solution modulo the product of those moduli. If you know a number's remainder when divided by 3, by 5, and by 7 separately, CRT tells you there is exactly one number modulo 105 = 3·5·7 consistent with all three remainders — and gives an explicit recipe for reconstructing it. This turns 'many small congruences' into 'one congruence mod the product,' which is why CRT underlies fast modular arithmetic in cryptography (RSA decryption is often accelerated by working mod p and mod q separately and recombining), coding theory, and the internal design of computer arithmetic.

An integer a is a quadratic residue modulo n if it is congruent to a perfect square modulo n — that is, x² ≡ a (mod n) has a solution. For an odd prime p, exactly half of the nonzero residues 1, …, p−1 are quadratic residues and half are non-residues, a symmetry first studied systematically by Euler and Legendre and brought to full power by Gauss's law of quadratic reciprocity (which he called his 'theorema aureum,' golden theorem, and proved multiple times over his career). The Legendre symbol (a/p) packages this as +1 (residue), −1 (non-residue), or 0 (a ≡ 0), and Euler's criterion gives a direct formula for it via modular exponentiation. Quadratic residues matter well beyond pure theory: they determine which numbers have modular square roots (needed to solve quadratic congruences), they underlie primality tests (Solovay–Strassen) and cryptographic constructions (Rabin cryptosystem, Goldwasser–Micali encryption), and reciprocity lets you decide residue-ness for huge primes without factoring anything.

A continued fraction expresses a number as an integer plus the reciprocal of another number, applied recursively: a₀ + 1/(a₁ + 1/(a₂ + 1/(a₃ + ⋯))). Every rational number has a finite continued fraction expansion, and computing it is literally the Euclidean algorithm run on the numerator and denominator — the quotients at each division step are exactly the continued-fraction terms. Irrational numbers get infinite expansions; famously, the expansion of an irrational is eventually periodic if and only if the number is a quadratic irrational (root of a degree-2 polynomial with integer coefficients), a theorem due to Lagrange. Truncating the expansion at each stage produces the 'convergents,' which are provably the best possible rational approximations to a given number for their denominator size — the reason continued fractions are used for calendar design (fractions of a year), gear ratios, and solving Pell's equation x² − Ny² = 1.

An integer g is a primitive root modulo n if its powers g, g², g³, … cycle through every unit (every residue coprime to n) before repeating — that is, g has the maximum possible multiplicative order, φ(n). When a primitive root exists, the group of units mod n is 'cyclic,' generated entirely by the single element g, which turns multiplication mod n into addition of exponents (a discrete analogue of logarithms). Gauss proved that primitive roots exist exactly for n = 1, 2, 4, pᵏ, and 2pᵏ where p is an odd prime — notably, they do NOT exist mod 8, 15, or any n with two distinct odd prime factors. Primitive roots are the engine behind discrete logarithms, which underlie Diffie–Hellman key exchange and the ElGamal cryptosystem: computing gˣ mod p is fast, but recovering x from gˣ (the discrete log problem) is believed to be hard.

A perfect number is a positive integer that equals the sum of its proper divisors (all divisors except itself) — for example 6 = 1 + 2 + 3. The Greeks, especially Euclid in the Elements, studied these numbers for their aesthetic and mystical appeal; Euclid proved that whenever 2ᵖ − 1 is prime (a 'Mersenne prime'), the number 2ᵖ⁻¹(2ᵖ − 1) is perfect. Over two thousand years later, Euler proved the converse: every EVEN perfect number must be of exactly this form, giving a complete classification of even perfect numbers tied one-to-one to Mersenne primes. Whether any odd perfect number exists is one of the oldest open problems in mathematics — none has ever been found, and it is known any odd perfect number (if it exists) would have to be astronomically large and satisfy many restrictive conditions.

The Möbius function μ(n), introduced by August Ferdinand Möbius in 1832, is a multiplicative function that detects square-free structure: μ(n) = 0 if n has a repeated prime factor, and otherwise μ(n) = (−1)^k where k is the number of distinct prime factors of n. It is the key ingredient of Möbius inversion, a technique that reverses sums over divisors — if g(n) = Σ_{d|n} f(d), then f(n) = Σ_{d|n} μ(d) g(n/d), letting you recover f from a divisor sum of it. This machinery appears throughout multiplicative number theory: it gives a formula for Euler's totient function φ(n) = Σ_{d|n} μ(d)·n/d, and the identity Σ_{d|n} μ(d) = [n = 1] (equal to 1 only when n = 1, else 0) is the discrete engine behind sieve methods and the analytic study of the prime-counting function via the Möbius function's connection to 1/ζ(s).

Fermat's theorem on sums of two squares (stated by Fermat in 1640, first published proof by Euler) answers a deceptively simple question: which primes can be written as a² + b² for integers a, b? The answer is exactly the primes p ≡ 1 (mod 4), plus the special case p = 2 = 1² + 1²; primes p ≡ 3 (mod 4) can NEVER be written as a sum of two squares. This single fact about primes controls which integers overall are expressible: a positive integer n is a sum of two squares if and only if every prime factor of n congruent to 3 mod 4 appears to an even power in its factorization. The theorem is a cornerstone of the arithmetic of Gaussian integers ℤ[i], where a prime p ≡ 1 (mod 4) factors as p = (a+bi)(a−bi), while primes p ≡ 3 (mod 4) stay prime (inert) in that ring.

Wilson's theorem says that an integer p > 1 is prime exactly when (p−1)! ≡ −1 (mod p). The statement is named for John Wilson, a student of Edward Waring who conjectured it in 1770 (Waring published it without proof); Lagrange gave the first proof in 1771, and there is evidence Leibniz knew the result nearly a century earlier. What makes it striking is that it is an if-and-only-if characterization of primality purely in terms of a factorial residue — no composite number can satisfy it, so in principle it is a primality test. In practice it is useless computationally, because computing (p−1)! mod p is far slower than trial division or modern probabilistic tests, but the theorem is a genuine gem of elementary number theory and a useful lemma in proofs (for instance, in results about primes of the form 4k+1 being a sum of two squares).

Euler's theorem, proved by Leonhard Euler in 1736 (the same paper that contains his proof of Fermat's little theorem), extends Fermat's result from prime moduli to any modulus n: for a coprime to n, a raised to the totient φ(n) is congruent to 1 modulo n. When n happens to be prime p, φ(p) = p − 1 and the statement collapses to Fermat's little theorem exactly, which is why Euler's theorem is often called its generalization. The practical payoff is enormous: it lets you reduce huge exponents modulo φ(n) instead of modulo n itself, which is exactly the trick that makes RSA decryption work (choosing exponents so that raising to them and back is the identity map modulo φ(n)) and is the standard tool for computing a^k mod n by hand or by fast exponentiation software when k is astronomically large.

The Legendre symbol (a/p), introduced by Adrien-Marie Legendre in 1798, is compact notation for whether an integer a is a quadratic residue modulo an odd prime p: it equals +1 if a is a nonzero square mod p, −1 if it is a non-residue, and 0 if p divides a. Beyond bookkeeping, the symbol is multiplicative in its top argument — (ab/p) = (a/p)(b/p) — which turns residue questions about products into simple sign arithmetic, and Euler's criterion gives a direct computational formula via modular exponentiation. Combined with Gauss's law of quadratic reciprocity, the Legendre symbol lets you decide, for arbitrarily large primes, whether a number is a square mod p without ever testing individual residues — a cornerstone technique feeding into primality tests (Solovay–Strassen) and the later, more general Jacobi and Kronecker symbols.

Pell's equation is x² − Ny² = 1, where N is a fixed nonsquare positive integer and integer solutions (x, y) are sought. Despite the name, Pell had little to do with it — Euler mistakenly attributed earlier work to John Pell, and the equation was studied far earlier, including a rich treatment by Indian mathematicians Brahmagupta (7th century) and Bhāskara II (12th century), who developed the chakravala method for solving it. Whenever N is not a perfect square, Pell's equation has infinitely many positive integer solutions, all generated from a single smallest one — the 'fundamental solution' — by a simple recurrence; if N is a perfect square, only the trivial solution (x, y) = (1, 0) exists, since the equation would factor over the integers. The fundamental solution is found directly from the continued fraction expansion of √N: it comes from the first convergent that satisfies the equation, and the theory guarantees this always happens within the periodic part of the expansion. Pell's equation shows up wherever quadratic irrationals do — rational approximation of √N, the study of units in real quadratic number fields, and classical geometric problems like the 'cattle problem' attributed to Archimedes.

An arithmetic function is simply a function defined on the positive integers, usually capturing something about a number's divisors or prime factorization: the divisor-counting function d(n) (also written τ(n)), the divisor-sum function σ(n), and Euler's totient φ(n) are the classic examples, alongside the Möbius function μ(n). What makes this family so useful is that most of them are multiplicative — f(mn) = f(m)f(n) whenever gcd(m, n) = 1 — which means each one is completely determined by its values on prime powers, and those values are easy to write down from a number's prime factorization. This turns hard-looking questions ('how many divisors does 360 have?') into quick prime-factorization exercises, and the same multiplicative structure underlies deep results like the Möbius inversion formula, Dirichlet convolution, and the study of perfect numbers (n with σ(n) = 2n).

Modular arithmetic is a system of arithmetic for integers where numbers 'wrap around' upon reaching a fixed value called the modulus — much like a clock face wraps from 12 back to 1. Two integers a and b are congruent modulo n (written a ≡ b (mod n)) if they leave the same remainder when divided by n, equivalently if n divides their difference. The modern systematic approach to number theory using modular arithmetic was developed by Carl Friedrich Gauss in his 1801 book Disquisitiones Arithmeticae. Modular arithmetic underlies clock/calendar calculations, checksums, hashing, and modern cryptography.

The fundamental theorem of arithmetic states that every integer greater than 1 is either prime or can be written as a product of primes in exactly one way, up to the order the factors are listed. This uniqueness is what makes primes the 'atoms' of multiplication — every whole number has one, and only one, prime 'chemical formula'.

RSA, named for its inventors Ron Rivest, Adi Shamir, and Leonard Adleman (1977), was the first practical public-key cryptosystem: it lets anyone encrypt a message using a public key while only the holder of a matching private key can decrypt it. Its security rests on a number-theoretic asymmetry — multiplying two large primes p and q together is fast, but factoring the product n = pq back into p and q is believed to be computationally infeasible for large enough primes. Key generation picks an encryption exponent e coprime to φ(n) = (p−1)(q−1) and computes the decryption exponent d as e's inverse modulo φ(n); encryption is c ≡ mᵉ (mod n) and decryption is m ≡ cᵈ (mod n). Correctness of decryption — that (mᵉ)ᵈ ≡ m (mod n) — follows directly from Euler's theorem (the generalization of Fermat's little theorem to composite moduli), since ed ≡ 1 (mod φ(n)) makes mᵉᵈ = m·m^{k·φ(n)} ≡ m·1ᵏ = m (mod n) whenever gcd(m,n)=1.

Algebraic number theory studies the arithmetic of algebraic number fields — finite extensions of the rational numbers. It generalises classical integer arithmetic by replacing \(\mathbb{Z}\) with rings of algebraic integers, revealing deep structure through ideals, class groups, and unit groups.

Class field theory is the crown jewel of algebraic number theory. It provides a complete classification of abelian extensions of a number field \(K\) in terms of arithmetic data intrinsic to \(K\) — specifically, its idèle class group. The Artin reciprocity map generalises both quadratic reciprocity and Dirichlet's theorem on primes in progressions.

A Dirichlet series is a series of the form \(\sum_{n=1}^\infty a_n n^{-s}\). The Riemann zeta function is the canonical example. L-functions are Dirichlet series with multiplicative coefficients attached to arithmetic objects (characters, elliptic curves, modular forms) and are central tools in analytic number theory.

Sieve methods are combinatorial techniques for counting or estimating integers in a set that are not divisible by primes in a prescribed list. The sieve of Eratosthenes is the simplest; modern sieves (Brun, Selberg, large sieve) yield sharp estimates for prime-related problems such as twin primes and Goldbach-type results.

An elliptic curve is a smooth projective cubic curve with a distinguished rational point, equipped with a group law that makes it an abelian group. Elliptic curves over finite fields underpin modern cryptography; over the rationals they are central to the Birch–Swinnerton-Dyer conjecture and Wiles's proof of Fermat's Last Theorem.

A quadratic residue modulo a prime \(p\) is an integer that is congruent to a perfect square mod \(p\). The Law of Quadratic Reciprocity — called by Gauss the 'golden theorem' — gives a beautifully symmetric criterion for when an odd prime is a square mod another odd prime.