Loading field map
Elementary number theory is the study of the integers—whole numbers, both positive and negative, and zero—and their properties. Its name distinguishes it not by simplicity but by method: it seeks to prove results about integers using techniques that do not rely on the advanced machinery of analysis, algebra, or geometry. This self-imposed restriction, historically a matter of necessity and later a matter of taste, gives the field its distinctive character. The subject asks deceptively simple questions about addition, multiplication, and divisibility, yet these questions have driven some of the most profound developments in mathematics.
At its core, elementary number theory investigates the multiplicative structure of the integers. The fundamental theorem of arithmetic states that every integer greater than 1 can be written uniquely as a product of prime numbers, up to the order of the factors. This single fact organizes the entire subject. Primes—integers greater than 1 with no positive divisors other than 1 and themselves—are the atoms of the number system, and much of number theory concerns their distribution and properties.
The field's enduring questions cluster around several themes. One is the distribution of primes: how many primes are there below a given bound, and how are they spaced? Euclid proved that there are infinitely many primes, but finer questions about their density and gaps remain active areas of research. Another theme is divisibility and the greatest common divisor, which leads to the Euclidean algorithm, a method for finding the greatest common divisor of two integers that has been known since antiquity and remains computationally important today.
A third theme is congruences. Two integers are congruent modulo a positive integer m if they differ by a multiple of m. This notion, formalized by Carl Friedrich Gauss in his 1801 work Disquisitiones Arithmeticae, allows arithmetic to be performed on the finite set of remainders {0, 1, ..., m−1}. Congruence equations, such as linear congruences ax ≡ b (mod m), and systems of such equations, are solved using the Chinese remainder theorem, which gives conditions under which a system of congruences with pairwise coprime moduli has a simultaneous solution.
A fourth theme concerns special types of integers and the equations they satisfy. Perfect numbers, which equal the sum of their proper divisors, have fascinated mathematicians since antiquity. Pythagorean triples—integer solutions to a² + b² = c²—were studied by the Babylonians and Greeks. Fermat's Last Theorem, which states that the equation xⁿ + yⁿ = zⁿ has no positive integer solutions for n > 2, is the most famous example of a Diophantine equation, an equation whose solutions are required to be integers. While Fermat's Last Theorem was ultimately proved using deep modern methods far beyond elementary techniques, many Diophantine equations of similar flavor remain approachable by elementary means.
The roots of elementary number theory lie in ancient civilizations. Babylonian clay tablets contain computations of Pythagorean triples, and Egyptian mathematics dealt with unit fractions and divisibility. Greek mathematicians, particularly the Pythagoreans and Euclid, made the first systematic contributions. Euclid's Elements (circa 300 BCE) contains the Euclidean algorithm, the proof of the infinitude of primes, and a proof that the square root of 2 is irrational—a result that arises from considering parity and divisibility. Diophantus of Alexandria, writing in the third century CE, studied equations requiring integer or rational solutions, and his work Arithmetica later inspired Fermat.
Indian mathematicians made substantial advances. Brahmagupta (seventh century CE) developed methods for solving quadratic Diophantine equations, including the Pell equation x² − Dy² = 1, and formulated the Chinese remainder theorem in a recognizable form. Later Indian mathematicians, including Bhāskara II, refined these methods. Islamic mathematicians preserved and extended Greek and Indian work, contributing to the theory of congruences and the study of perfect numbers.
The modern era of elementary number theory began in the seventeenth century with Pierre de Fermat. Working largely in the margins of Diophantus's Arithmetica, Fermat stated numerous results without proof, including his famous Last Theorem and the theorem that every prime of the form 4k + 1 can be expressed as the sum of two squares. Fermat also developed the method of infinite descent, a powerful technique for proving nonexistence of solutions by showing that any solution would generate a smaller one, leading to a contradiction.
Gauss's Disquisitiones Arithmeticae transformed the subject. He systematized the theory of congruences, introduced the notation a ≡ b (mod m), proved the law of quadratic reciprocity—a deep theorem relating the solvability of two related quadratic congruences—and developed the theory of quadratic forms. Gauss's work established elementary number theory as a coherent discipline with its own methods and standards of rigor.
Throughout the nineteenth century, mathematicians including Legendre, Dirichlet, and Chebyshev extended the subject. Dirichlet proved that any arithmetic progression a, a + d, a + 2d, ... with gcd(a, d) = 1 contains infinitely many primes, a result that uses analytic methods and thus lies outside the elementary tradition, though its statement is purely number-theoretic. The distinction between elementary and analytic number theory became explicit in the twentieth century, when the prime number theorem—describing the asymptotic density of primes—was first proved using complex analysis, and only later given an elementary proof by Paul Erdős and Atle Selberg in 1949.
Elementary number theory is defined less by its objects than by its methods. Several distinct approaches coexist, each with its own strengths and limitations.
The Euclidean tradition centers on divisibility and the algorithm named after Euclid. This approach emphasizes constructive methods: finding greatest common divisors, solving linear Diophantine equations, and computing with continued fractions. Its power lies in its concreteness and algorithmic nature. The Euclidean algorithm is one of the oldest and most practical tools in mathematics, and its generalizations underpin modern computational number theory and cryptography.
The congruence approach, systematized by Gauss, treats the integers through their remainders modulo m. This perspective reveals periodic structure and allows problems to be reduced to finite computations. The theory of congruences leads naturally to the concept of the multiplicative group of units modulo m, which has order φ(m), where φ is Euler's totient function counting the integers between 1 and m that are coprime to m. Fermat's little theorem—that aᵖ ≡ a (mod p) for prime p—and Euler's generalization a^φ(m) ≡ 1 (mod m) for gcd(a, m) = 1 are central results of this approach. These theorems are not merely abstract: they form the basis of the RSA cryptosystem, one of the most widely used encryption methods.
The Diophantine tradition focuses on solving equations in integers or rational numbers. This approach is characterized by ingenuity and case-by-case analysis, though it also includes general methods such as infinite descent and the theory of Pell equations. The difficulty of Diophantine problems varies enormously; some yield to elementary arguments, while others, like Fermat's Last Theorem, resist centuries of effort and require entirely new mathematical frameworks. The Diophantine tradition connects elementary number theory to algebraic geometry and the modern theory of elliptic curves, though those connections lie beyond the elementary scope.
The additive and combinatorial approach studies how integers can be represented as sums of other integers. Goldbach's conjecture—that every even integer greater than 2 is the sum of two primes—is a famous open problem in this vein. Waring's problem asks whether every positive integer can be expressed as a sum of a fixed number of k-th powers. These problems often admit elementary partial results, though their complete solutions typically require analytic methods.
The computational approach has become increasingly prominent. Elementary number theory provides algorithms for primality testing, factorization, and modular arithmetic that are both theoretically interesting and practically essential. The distinction between problems that are easy (solvable in polynomial time) and hard (believed to require exponential time) has reshaped the field's priorities. The difficulty of factoring large integers, for instance, is the basis of RSA security, while the ease of modular exponentiation enables efficient encryption and decryption.
These approaches are not mutually exclusive. A single problem may be attacked from multiple directions, and results from one approach often illuminate another. The law of quadratic reciprocity, for example, can be stated in terms of congruences, proved by combinatorial counting arguments, and interpreted through the theory of quadratic forms. The unity of the subject lies in its focus on the integers and the interplay between these different perspectives.
Contemporary elementary number theory is a mature field with a clear sense of its own boundaries. Its core results—the fundamental theorem of arithmetic, the Euclidean algorithm, the Chinese remainder theorem, Fermat's little theorem, quadratic reciprocity—are settled and form the backbone of the subject. These results are taught in undergraduate courses and are essential tools for mathematicians in many fields.
The field's open problems are notable for their simplicity of statement and difficulty of proof. Goldbach's conjecture, the twin prime conjecture (that there are infinitely many pairs of primes differing by 2), and the question of whether there are infinitely many perfect numbers remain unresolved. These problems are not merely curiosities; they test the limits of current mathematical understanding and motivate the development of new techniques.
The relationship between elementary and nonelementary methods is a defining feature of the modern field. Some results, like the prime number theorem, were first proved by analytic means and only later given elementary proofs. Others, like Dirichlet's theorem on primes in arithmetic progressions, still lack elementary proofs. The term "elementary" in this context means "not using analysis or advanced algebra," not "easy." Some elementary proofs are extraordinarily intricate, and some analytic proofs are conceptually simpler than their elementary counterparts.
The field's practical applications have grown dramatically. Public-key cryptography relies on the computational difficulty of factoring and the discrete logarithm problem, both of which are grounded in elementary number theory. Error-correcting codes, pseudorandom number generators, and hash functions all draw on the subject's results. These applications have given elementary number theory a new relevance, though they have not changed its fundamental character as a pure mathematical discipline.
Elementary number theory remains an active area of research, particularly in its computational and algorithmic aspects. Primality testing, factorization algorithms, and the study of pseudoprimes—composite numbers that behave like primes in certain tests—are ongoing concerns. The field also continues to inspire amateurs, as it always has; its problems are easy to state and understand, yet deep enough to reward serious study. This accessibility, combined with its central position in mathematics, ensures that elementary number theory will remain a vital and inviting subject.