- Atlas
- Mathematics
- Elementary Number Theory
Elementary Number Theory
Elementary number theory is the study of the integers—the whole numbers—using methods that stay close to arithmetic itself: divisibility, remainders, factorization, and the solving of equations in whole numbers.
9 frameworks, from 300 BCE to today · Number Theory · Mathematics
- Divisibility and Euclidean arithmetic 300 BCE-Present
- Diophantine equation 250-Present
- Arithmetic functions and multiplicative structure 1730-Present
- Continued fraction 1730-Present
- Quadratic forms and representation 1770-Present
- Modular arithmetic 1801-Present
- Quadratic reciprocity 1801-Present
- Elementary proofs of analytic results 1850-Present
- Computational number theory 1976-Present
Overview
Elementary number theory is the study of the integers—the whole numbers—using methods that stay close to arithmetic itself: divisibility, remainders, factorization, and the solving of equations in whole numbers1. What makes it a field rather than a grab-bag of puzzles is that its questions are simple to state and its answers often require ideas of startling depth1. Which numbers divide which? How are the primes arranged1? Which equations have whole-number solutions, and how many1? The history of the subject is the history of tools invented to answer such questions—and of the repeated discovery that "elementary" does not mean "easy."
Divisibility and the Euclidean foundation
The oldest layer is divisibility1. Euclid's Elements (c. 300 BCE) contains what we now call the Euclidean algorithm for finding the greatest common divisor of two integers by repeated subtraction and remainder, and from it the theorem that every integer factors uniquely into primes. That uniqueness—the fundamental theorem of arithmetic—looks obvious but is a genuine theorem, and its failure in larger number systems (such as the integers extended by √−5) became one of the great engines of nineteenth-century algebra1.
Euclid also proved that there are infinitely many primes, by the argument that any finite list of primes can be multiplied together and one added to produce a number with a new prime factor. This is the model of an elementary proof: no analysis, no limits, just arithmetic. Greek mathematicians also studied perfect numbers and figured numbers, and Diophantus of Alexandria, in the third century CE, wrote the Arithmetica, a collection of problems on finding rational and integer solutions to equations1. His name survives in "Diophantine equations"—polynomial equations solved in whole or rational numbers—though Diophantus himself usually sought rational solutions and lacked a general method.
Congruences: Gauss and modular arithmetic
The decisive transformation came with Carl Friedrich Gauss's Disquisitiones Arithmeticae (1801)123. Gauss introduced the notation and theory of congruences: two integers are congruent modulo n if their difference is divisible by n13. This turns remainders into an arithmetic of their own—clock arithmetic—in which one can add, subtract, and multiply, and in which the question "does this equation have a solution?" becomes a question about residue classes1. The gain is enormous: a statement about all integers can often be reduced to a finite check over residues.
Gauss proved the law of quadratic reciprocity, which he called the "golden theorem."14 It answers when one prime is a square modulo another: for odd primes p and q, the answer for p modulo q is tied to the answer for q modulo p, with a sign depending on the residues of p and q modulo 4. The law had been conjectured by Euler and Legendre; Gauss gave the first complete proof and returned to it repeatedly, producing several more4. Its importance is hard to overstate: it is the first deep structural statement about primes, and its many proofs—elementary, algebraic, analytic—became a testing ground for new methods. Gauss also developed the theory of binary quadratic forms, expressions like ax² + bxy + cy², classifying them by discriminant and composition, work that later flowered into algebraic number theory and the class group.
Fermat, Euler, and the arithmetic of functions
Pierre de Fermat, in the seventeenth century, left a body of claims and methods: his little theorem (if p is prime and a is not divisible by p, then a^p−1 ≡ 1 mod p), his work on sums of two squares, and the famous marginal note that became Fermat's Last Theorem156. Leonhard Euler, in the eighteenth century, turned much of this into systematic theory1. He proved Fermat's little theorem, generalized it, and introduced the totient function φ(n), counting integers up to n that are coprime to n1578. He discovered the product formula relating the sum of 1/n^s over all n to a product over primes—the seed of the Riemann zeta function—and used it to prove that the sum of reciprocals of the primes diverges, a first quantitative statement about how densely primes are spread.
Euler also pioneered the use of arithmetic functions: functions of n defined by divisibility, such as the number of divisors d(n) and the sum of divisors σ(n). The key structural notion is multiplicativity—a function f is multiplicative if f(mn) = f(m)f(n) whenever m and n are coprime—which lets a function be understood prime by prime9. This "multiplicative structure" became a organizing principle: many questions about integers reduce to questions about their prime factorization, and functions that respect that factorization are the natural objects of study.
Continued fractions and rational approximation
A parallel tradition concerns how well a rational number can approximate an irrational one. The continued fraction expansion of a real number—writing it as a nested sequence of integer quotients—gives, at each stage, a rational approximation that is in a precise sense the best possible for its denominator size1011. Euler and Lagrange developed the theory in the eighteenth century; Lagrange proved that the expansion is eventually periodic exactly for quadratic irrationals, a striking link between arithmetic and approximation. The theory of continued fractions became a standard tool for solving Pell's equation x² − Dy² = 1 in integers, and for understanding the fine structure of rational approximations, including the fact that the golden ratio is the "most badly approximable" number.
Quadratic forms and representation
The question of which integers are represented by a given quadratic form—which n can be written as x² + y², or as x² + 2y², or by a general binary form—runs from Fermat and Euler through Gauss and Legendre to a large nineteenth-century literature. Fermat's two-squares theorem (an odd prime is a sum of two squares exactly when it is 1 modulo 4) is the model case12. The general theory classifies forms by their discriminant and studies composition of forms, and it connects directly to quadratic reciprocity and to the arithmetic of quadratic fields. In the twentieth century the subject was recast in the language of modular forms and theta series, but the elementary core—local conditions plus a representation problem—remains a standard entry point.
Elementary proofs of analytic results
A recurring theme is the tension between analytic and elementary methods. The prime number theorem—that the number of primes up to x is asymptotic to x/log x—was proved in 1896 by Hadamard and de la Vallée Poussin using complex analysis. It had been conjectured by Gauss and Legendre from numerical evidence. In 1949 Atle Selberg and Paul Erdős gave "elementary" proofs, meaning proofs avoiding complex analysis (though not avoiding real analysis and limits)1. The episode is instructive: "elementary" is a statement about the tools used, not about difficulty, and the search for elementary proofs has repeatedly clarified what is essential to a result. Elementary methods also produced results like Chebyshev's bounds on the prime-counting function, which bracket the truth without proving the asymptotic13.
Computation and the modern algorithmic turn
Number theory has always been computational—tables of primes, factorizations, and residues were central to Gauss's and Legendre's work—but the twentieth century made algorithms a subject in their own right. The Euclidean algorithm, the sieve of Eratosthenes, and modular exponentiation are ancient or classical; the modern era added fast primality testing, integer factorization methods, and the use of number theory in cryptography, beginning with the Diffie–Hellman key exchange (1976) and RSA (1977). These developments fed back into elementary theory: the study of congruences, quadratic residues, and modular arithmetic became the practical foundation of public-key systems, and the analysis of algorithms gave new questions about how fast elementary operations can be performed714.
The present
Elementary number theory today is both a teaching subject and a research toolkit1. Its classical core—divisibility, congruences, quadratic reciprocity, arithmetic functions, quadratic forms, continued fractions, Diophantine equations—remains the standard first course in number theory and the common language of the field. Research uses these tools constantly, often as the "elementary" layer beneath algebraic and analytic machinery: a congruence computation, a reciprocity law, or a representation by a quadratic form is frequently the concrete check on a deep theory. Open questions remain close to the surface—the distribution of primes in arithmetic progressions, the exact set of integers represented by a given form, the effective solution of Diophantine equations—and the boundary between elementary and advanced methods is itself an active question, as the history of the prime number theorem shows.
References
- Number theory (introduction, Definition, Elementary number theory, Analytic number theory, Diophantine geometry, History, Algebraic number theory, Applications), Wikipedia
- Quadratic form (History), Wikipedia
- Modular arithmetic, Wikipedia
- Quadratic reciprocity, Wikipedia
- Fermat's little theorem (introduction, History), Wikipedia
- Fermat's Last Theorem, Wikipedia
- Euler's theorem, Wikipedia
- Euler's totient function (History, terminology, and notation), Wikipedia
- Multiplicative function, Wikipedia
- Continued fraction, Wikipedia
- Diophantine approximation, Wikipedia
- Binary quadratic form, Wikipedia
- Prime number theorem (History of the proof of the asymptotic law of prime numbers), Wikipedia
- Modular multiplicative inverse, Wikipedia
The frameworks of Elementary Number Theory
Each framework is a way of working the field has used: when it held, and the question it answers.
- 300 BCE-Present
Divisibility and Euclidean arithmetic
How do whole numbers divide and factor?
- 250-Present
- 1730-Present
Arithmetic functions and multiplicative structure
How do divisor-based functions behave prime by prime?
- 1730-Present
Continued fraction
How well can fractions approximate irrational numbers?
- 1770-Present
Quadratic forms and representation
Which numbers does a quadratic form represent?
- 1801-Present
- 1801-Present
- 1850-Present
Elementary proofs of analytic results
Can deep counting results be proved by plain arithmetic?
- 1976-Present
Computational number theory
How fast can number-theoretic tasks be computed?
How the ideas connect
Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.
Modular arithmetic grew out of Divisibility and Euclidean arithmetic
Gauss's congruence arithmetic is a direct refinement of Euclidean division with remainder: congruence modulo n is defined by divisibility of the difference, and the residue classes inherit the arithmetic of the integers.
Carried by Carl Friedrich Gauss; Disquisitiones Arithmeticae (1801).
Computational number theory influenced by Modular arithmetic
Public-key cryptography from Diffie-Hellman and RSA rests directly on modular arithmetic and modular exponentiation; the practical security questions drove the modern algorithmic study of congruences.
Carried by Whitfield Diffie; Martin Hellman; Rivest, Shamir and Adleman.
Diophantine equation influenced by Divisibility and Euclidean arithmetic
Diophantus's Arithmetica worked problems in rational and integer solutions using divisibility and factorization techniques inherited from the Euclidean arithmetic tradition. The Euclidean algorithm and unique factorization supplied the tools for reducing Diophantine problems.
Carried by Euclid; Diophantus.
Arithmetic functions and multiplicative structure influenced by Divisibility and Euclidean arithmetic
Euler built the theory of arithmetic functions on divisibility: divisor counts and divisor sums are defined through the Euclidean factorization of n, and multiplicativity rests on unique prime factorization.
Carried by Leonhard Euler.
Continued fraction influenced by Divisibility and Euclidean arithmetic
The Euclidean algorithm is the engine of continued fractions: the quotients in the expansion of a rational are exactly the quotients produced by repeated division with remainder.
Carried by Leonhard Euler.
Quadratic forms and representation influenced by Divisibility and Euclidean arithmetic
The theory of binary quadratic forms grew from divisibility and congruence questions about which numbers are represented; Fermat's two-squares theorem was proved using elementary descent on divisibility.
Carried by Pierre de Fermat; Leonhard Euler.
Computational number theory influenced by Divisibility and Euclidean arithmetic
The Euclidean algorithm and the sieve of Eratosthenes became core computational primitives, and the analysis of how fast gcd and factorization can be performed is a direct study of these classical procedures.
Carried by Euclid.
Continued fraction influenced by Diophantine equation
The continued fraction expansion was developed in part as a tool for solving Pell's equation x^2 - Dy^2 = 1, a Diophantine problem; Lagrange used the periodicity of the expansion to solve it.
Carried by Joseph-Louis Lagrange.
Quadratic forms and representation influenced by Diophantine equation
Fermat's and Euler's questions about which integers are sums of squares or represented by forms like x^2 + 2y^2 were Diophantine representation problems that became the model cases of the general theory of quadratic forms.
Carried by Pierre de Fermat; Leonhard Euler.
Elementary proofs of analytic results influenced by Arithmetic functions and multiplicative structure
Euler's product formula and his proof that the sum of reciprocal primes diverges supplied the arithmetic-function machinery that later elementary treatments of prime distribution, such as Chebyshev's bounds, built upon.
Carried by Leonhard Euler; Pafnuty Chebyshev.
Quadratic reciprocity influenced by Quadratic forms and representation
Gauss's classification of binary quadratic forms by discriminant and his composition of forms were developed alongside and fed into his treatment of quadratic reciprocity, the two theories being intertwined in the Disquisitiones.
Carried by Carl Friedrich Gauss.
Computational number theory influenced by Quadratic reciprocity
Quadratic residues and reciprocity laws became practical tools in primality testing and in the design of cryptographic schemes, feeding concrete congruence computations into algorithmic number theory.
Beyond the field
Where Elementary Number Theory's ideas came from in other fields, and what they led to there: the strongest 12 of 42 links.
Arithmetic functions and multiplicative structure led to Pretentious Multiplicative Function Theory in Analytic Number Theory
Pretentious multiplicative function theory is a refinement of the classical theory of arithmetic functions and multiplicative structure, recasting multiplicative functions in terms of a 'distance' to a pretentious model. It grew directly out of the classical study of multiplicative functions and their mean values.
Carried by Andrew Granville; K. Soundararajan.
Quadratic forms and representation influenced Hasse principle in Arithmetic Geometry
The Hasse principle was first proved for quadratic forms: Hasse's work on quadratic forms over number fields established that local representability implies global representability, making the theory of quadratic forms the model case.
Carried by Helmut Hasse.
Elementary proofs of analytic results reacted against Analytic number theory in Number Theory
Elementary proofs of analytic results took shape as a reaction to analytic number theory, aiming to reprove its theorems, such as the prime number theorem, by elementary means. The programme is defined by its rejection of analytic methods.
Computational number theory influenced Public-key cryptography in Computational Number Theory
Elementary computational number theory, especially modular arithmetic and primality testing, provided the concrete operations and hardness assumptions behind the first public-key systems of 1976–77.
Carried by Whitfield Diffie; Martin Hellman.
Computational number theory influenced Quantum algorithms for number theory in Computational Number Theory
Elementary computational number theory, especially modular exponentiation and order finding, provided the concrete problems that Shor's quantum algorithms for factoring and discrete logarithms addressed.
Carried by Peter Shor.
Divisibility and Euclidean arithmetic influenced Elementary and algorithmic number theory in Number Theory
Gauss's Disquisitiones Arithmeticae built the congruence calculus directly on Euclidean divisibility and the Euclidean algorithm, recasting them as the foundation of elementary number theory. The later algorithmic tradition inherits this Euclidean base.
Carried by Carl Friedrich Gauss; Disquisitiones Arithmeticae (1801).
Divisibility and Euclidean arithmetic influenced Ideal Theory and Dedekind Domains in Algebraic Number Theory
Kummer and Dedekind generalised elementary divisibility and Euclidean arithmetic in rings of integers: the failure of unique factorization in cyclotomic integers led Kummer to ideal numbers and Dedekind to ideals. Divisibility theory is the direct ancestor of ideal theory.
Carried by Ernst Eduard Kummer; Richard Dedekind.
Divisibility and Euclidean arithmetic influenced Euler Product and Zeta Function Analysis in Analytic Number Theory
Euler's product formula rests on unique prime factorisation and the Euclidean divisibility framework; the divergence of the harmonic series over primes was his route to proving infinitely many primes.
Carried by Leonhard Euler.
Diophantine equation influenced Transcendental number theory in Number Theory
Liouville's construction of transcendental numbers and his approximation theorem were motivated by and applied to Diophantine equations, notably the impossibility of certain algebraic equations with rational approximations. The later theory of transcendence grew out of these Diophantine questions.
Carried by Joseph Liouville.
Arithmetic functions and multiplicative structure influenced Elementary and algorithmic number theory in Number Theory
Gauss and later elementary number theorists worked with arithmetic functions such as the divisor function and Euler's phi, whose multiplicative properties are central to the elementary theory. The later framework inherits this multiplicative-function apparatus.
Carried by Carl Friedrich Gauss; Leonhard Euler.
Arithmetic functions and multiplicative structure influenced Generating function in Enumerative Combinatorics
Euler's work on arithmetic functions and multiplicative structure, especially his 1740s papers on partitions and divisor sums, used and helped develop generating-function methods. Dirichlet series and Euler products for arithmetic functions became standard generating functions.
Carried by Leonhard Euler.
Arithmetic functions and multiplicative structure influenced Arithmetic combinatorics in Harmonic Analysis
The theory of arithmetic functions and multiplicative structure, from Euler and Dirichlet onward, supplied the objects (divisor functions, multiplicative functions) that arithmetic combinatorics counts and estimates.
Carried by Peter Gustav Lejeune Dirichlet.

Elementary Number Theory is a planet in Nousfarer
Its city has a tower for each of these 9 frameworks. Land, walk in, and climb one concept at a time.
Land on Elementary Number TheoryRelated fields
Fields its ideas are linked to
- Number Theory 14 links
- Computational Number Theory 5 links
- Analytic Number Theory 4 links
- Enumerative Combinatorics 3 links
- Harmonic Analysis 2 links
- Algebra 2 links
- Additive Number Theory 2 links
- Algebraic Number Theory 2 links
- Arithmetic Geometry 2 links
- Transcendental Number Theory 2 links
- Linear Algebra 1 link
- Algorithms 1 link
More in Number Theory
- Additive Number Theory
- Algebraic Number Theory
- Analytic Number Theory
- Arithmetic Geometry
- Computational Number Theory
- Modular Forms And Automorphic Forms
- Number Theory
- Transcendental Number Theory
See where Elementary Number Theory sits on the Map of Human Knowledge