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

still a working view ended · each leads to its entry below

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

  1. Number theory (introduction, Definition, Elementary number theory, Analytic number theory, Diophantine geometry, History, Algebraic number theory, Applications), Wikipedia
  2. Quadratic form (History), Wikipedia
  3. Modular arithmetic, Wikipedia
  4. Quadratic reciprocity, Wikipedia
  5. Fermat's little theorem (introduction, History), Wikipedia
  6. Fermat's Last Theorem, Wikipedia
  7. Euler's theorem, Wikipedia
  8. Euler's totient function (History, terminology, and notation), Wikipedia
  9. Multiplicative function, Wikipedia
  10. Continued fraction, Wikipedia
  11. Diophantine approximation, Wikipedia
  12. Binary quadratic form, Wikipedia
  13. Prime number theorem (History of the proof of the asymptotic law of prime numbers), Wikipedia
  14. 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.

  1. 300 BCE-Present
  2. 250-Present

    Diophantine equation

    Which equations have whole-number solutions?

    Fly to its tower in Nousfarer

  3. 1730-Present

    Arithmetic functions and multiplicative structure

    How do divisor-based functions behave prime by prime?

    Fly to its tower in Nousfarer

  4. 1730-Present

    Continued fraction

    How well can fractions approximate irrational numbers?

    Fly to its tower in Nousfarer

  5. 1770-Present

    Quadratic forms and representation

    Which numbers does a quadratic form represent?

    Fly to its tower in Nousfarer

  6. 1801-Present

    Modular arithmetic

    How does arithmetic work with remainders?

    Fly to its tower in Nousfarer

  7. 1801-Present

    Quadratic reciprocity

    When is one prime a square modulo another?

    Fly to its tower in Nousfarer

  8. 1850-Present

    Elementary proofs of analytic results

    Can deep counting results be proved by plain arithmetic?

    Fly to its tower in Nousfarer

  9. 1976-Present

    Computational number theory

    How fast can number-theoretic tasks be computed?

    Fly to its tower in Nousfarer

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.

Divisibility and Euclidean arithmeticDiophantine equationArithmetic functions and multiplicati…Continued fractionQuadratic forms and representationModular arithmeticQuadratic reciprocityElementary proofs of analytic resultsComputational 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.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

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 Theory

Related fields

Fields its ideas are linked to

More in Number Theory

See where Elementary Number Theory sits on the Map of Human Knowledge