Number Theory: Integers, Primes, and Divisibility

Number theory sits at the oldest and arguably most surprising corner of mathematics — the study of integers, prime numbers, and the hidden structure that governs how whole numbers relate to each other. This page covers the core definitions, the mechanisms behind divisibility and primality, and the practical scenarios where number theory appears, from classroom problem sets to cryptographic infrastructure that secures modern digital communication.

Definition and scope

A prime number has exactly 2 distinct positive divisors: 1 and itself. That deceptively simple definition has kept mathematicians occupied for roughly 2,300 years. As of 2024, the largest known prime number — discovered through the Great Internet Mersenne Prime Search (GIMPS) — contains over 41 million digits. That is not a typographical error. Forty-one million digits, for a number whose defining property is that nothing divides it cleanly except 1 and itself.

Number theory, as a formal discipline, concerns the properties of integers (the set {…, −3, −2, −1, 0, 1, 2, 3, …}) and the relationships among them. Its major sub-domains include:

The Millennium Prize Problems, maintained by the Clay Mathematics Institute, include the Riemann Hypothesis — a statement about the distribution of prime numbers that has resisted proof since Bernhard Riemann posed it in 1859. The prize for solving it is $1,000,000 (Clay Mathematics Institute).

For foundational concepts connecting number theory to broader mathematical thinking, Mathematics Authority's main index provides orientation across the discipline's major branches.

How it works

Divisibility is the engine at the center of number theory. An integer a divides integer b (written a | b) if there exists some integer k such that b = a × k. For example, 7 | 42 because 42 = 7 × 6. This sounds elementary — and it is — but the consequences ramify in unexpected directions.

The Fundamental Theorem of Arithmetic, formalized by Carl Friedrich Gauss in his 1801 Disquisitiones Arithmeticae, states that every integer greater than 1 can be expressed as a product of primes in exactly one way (up to ordering). The number 360 = 2³ × 3² × 5, and there is no other prime factorization for it. That uniqueness is not obvious, and proving it requires careful argument.

Three core tools structure most elementary number theory work:

  1. Greatest Common Divisor (GCD) — the largest integer dividing both a and b; computed efficiently by the Euclidean Algorithm (c. 300 BCE, documented in Euclid's Elements)
  2. Least Common Multiple (LCM) — the smallest positive integer divisible by both a and b; related to GCD by the identity LCM(a, b) × GCD(a, b) = |a × b|
  3. Modular arithmetic — a system where numbers "wrap around" after reaching a modulus; 17 mod 5 = 2 because 17 = 3 × 5 + 2

Modular arithmetic is not just a classroom exercise. The RSA encryption algorithm, standardized by NIST in FIPS 186-5, relies entirely on the computational difficulty of factoring large integers — a direct application of prime structure in number theory.

For those building toward number theory basics from an arithmetic foundations background, the Euclidean Algorithm is usually the first encounter with a non-trivial integer procedure.

Common scenarios

Number theory appears in three distinct contexts that look quite different on the surface.

Classroom and competition mathematics. Problems involving divisibility, prime factorization, and modular arithmetic appear throughout the Common Core State Standards for Mathematics, specifically in the Number System domain beginning in Grade 6. Mathematics competitions in the US — including MATHCOUNTS and the American Mathematics Competitions (AMC) series — regularly feature number theory problems as a distinct category.

Cryptography and digital security. RSA public-key cryptography, Diffie-Hellman key exchange, and elliptic-curve cryptography all depend on number-theoretic hardness assumptions. The NIST Post-Quantum Cryptography Standardization project — which released its first finalized standards in 2024 — is itself a response to the threat that quantum computers could factor large integers efficiently using Shor's algorithm, dismantling RSA security.

Pure mathematical research. Open problems in number theory have a habit of being easy to state and extraordinarily hard to prove. Goldbach's Conjecture (every even integer greater than 2 is the sum of 2 primes) has been verified computationally for every even number up to 4 × 10¹⁸ (Oliveira e Silva, 2013), yet no general proof exists. The Millennium Prize Problems page covers the Riemann Hypothesis, where the stakes — for both mathematics and cryptography — are difficult to overstate.

Decision boundaries

Number theory's internal distinctions matter when choosing methods and framing problems.

Prime vs. composite. A prime has exactly 2 divisors; a composite has 3 or more. The integer 1 is neither — a deliberate classification that preserves the uniqueness in the Fundamental Theorem of Arithmetic. Getting this boundary wrong propagates errors through any factorization argument.

Elementary vs. analytic methods. Elementary number theory avoids calculus and complex analysis; analytic number theory deploys them. The first proof of the Prime Number Theorem (1896, independently by Hadamard and de la Vallée Poussin) was analytic. An elementary proof came only in 1949 (Selberg and Erdős) — and the mathematical community considered it a genuine shock that one existed at all.

Exact divisibility vs. modular congruence. These address different questions. Does 7 divide 42? (yes, exactly) is a different question from What is 42 mod 8? (answer: 2). Both appear in mathematical proof techniques, but confusing the frameworks generates errors quickly.

Deterministic vs. probabilistic primality tests. The Miller-Rabin test is probabilistic — it can declare a composite number "probably prime" with some small error rate. The AKS primality test (Agrawal, Kayal, Saxena, 2002) is deterministic and runs in polynomial time, settling a question that had been open for decades. For cryptographic applications, NIST SP 800-131A specifies minimum key lengths and acceptable primality-testing methods.

References