Number Theory

Number Theory is the study of the integers

Z

and their arithmetic structure — divisibility, primes, congruences, and Diophantine equations. Key result in words: every integer greater than 1 factors uniquely into primes, and the distribution and behavior of those primes underlie nearly all of arithmetic. Where it applies: cryptography, coding theory, computer algebra, and pure mathematics. Who/when: from Euclid (~300 BCE) and Diophantus through Fermat, Euler, Gauss (Disquisitiones Arithmeticae, 1801), to modern analytic and algebraic number theory.

Number theory is the branch of mathematics concerned with the properties of the integers and, more broadly, with rings and fields that generalize them. At its undergraduate core it studies divisibility, the prime numbers, modular arithmetic (congruences), quadratic residues and reciprocity, multiplicative arithmetic functions, and the solution of equations in integers (Diophantine analysis). It matters because the integers are the foundation of all counting and computation, and because deep regularities — like unique factorization and quadratic reciprocity — turn out to govern everything from error-correcting codes to public-key cryptography. A surprising fact: although primes appear erratically, their large-scale density obeys an astonishingly precise law, $π (x) \sim x / ln x$ (the Prime Number Theorem), connecting the discrete world of integers to the continuous machinery of complex analysis.

The Core Insight

The integers are not a featureless set: they carry a rigid multiplicative skeleton built from the primes, the indivisible atoms of arithmetic. Two engines drive the whole subject. First, unique factorization (the Fundamental Theorem of Arithmetic) lets us reduce questions about all integers to questions about primes. Second, congruence (working modulo $n$ ) partitions the infinite integers into a finite arithmetic system $Z / n Z$ , where addition, multiplication, and even "square roots" can be analyzed exhaustively. Almost every classical theorem — Fermat's little theorem, Euler's theorem, the Chinese Remainder Theorem, quadratic reciprocity — is a statement about the structure of these finite systems and how the primes thread through them.

Formal Statement

Divisibility and Primes

For integers $a, b$ with $a \neq = 0$ , we say $a$ divides $b$ (written $a ∣ b$ ) if there exists an integer $k$ with $b = ak$ . A prime $p > 1$ is an integer whose only positive divisors are $1$ and $p$ . An integer $n > 1$ that is not prime is composite. The greatest common divisor $g cd (a, b)$ is the largest positive integer dividing both $a$ and $b$ ; if $g cd (a, b) = 1$ , $a$ and $b$ are coprime.

Fundamental Theorem of Arithmetic

Every integer $n > 1$ can be written as a product of primes, and this factorization is unique up to the order of the factors:

n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}}, p_{1} < p_{2} < \dots < p_{k}, a_{i} \geq 1.

⟳existence by strong induction (split any composite into smaller factors); uniqueness from Euclid's Lemma — if

p ∣ ab

then

p ∣ a

p ∣ b

Congruence

For a positive integer $n$ (the modulus), integers $a$ and $b$ are congruent modulo $n$ , written $a \equiv b (mod n)$ , if $n ∣ (a - b)$ . This is an equivalence relation partitioning $Z$ into $n$ residue classes, forming the ring $Z / n Z$ .

a \equiv b (mod n) ⟺ a - b = k n for some k \in Z .

⟳directly from the definition of divisibility applied to the difference

a - b

Bézout's Identity

For integers $a, b$ not both zero, there exist integers $x, y$ such that

a x + b y = g cd (a, b) .

⟳

g cd (a, b)

is the smallest positive value of

a x + b y

; run the Extended Euclidean Algorithm to produce explicit

x, y

Fermat's Little Theorem & Euler's Theorem

If $p$ is prime and $p ∤ a$ , then $a^{p - 1} \equiv 1 (mod p)$ . More generally, if $g cd (a, n) = 1$ ,

a^{φ (n)} \equiv 1 (mod n),

where $φ (n)$ is Euler's totient — the count of integers in ${1, \dots, n}$ coprime to $n$ .

⟳the units mod

n

form a group of order

φ (n)

; apply Lagrange's theorem (order of an element divides group order).

Quadratic Reciprocity

For distinct odd primes $p, q$ , with the Legendre symbol $(\frac{a}{p}) = \pm 1$ recording whether $a$ is a nonzero square mod $p$ ,

(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} .

⟳Gauss's lemma counts sign changes of multiples of

a

in a half-residue system; Eisenstein's lattice-point argument geometrizes the exponent.

Prime Number Theorem

Letting $π (x)$ count primes $\leq x$ ,

π (x) \sim \frac{x}{ln x}, equivalently x \to \infty lim \frac{π ( x ) ln x}{x} = 1.

⟳relate

π (x)

to the Riemann zeta function via the Euler product; the key analytic input is that

ζ (s)

has no zeros on the line

ℜ (s) = 1

Why It Holds / Derivation

Uniqueness in the Fundamental Theorem of Arithmetic

We prove uniqueness, given existence.

Euclid's Lemma. Suppose $p$ is prime and $p ∣ ab$ . If $p ∤ a$ , then $g cd (p, a) = 1$ (since $p$ 's only divisors are $1, p$ ). By Bézout (eq. [3]) there are integers $x, y$ with $p x + a y = 1$ .
Multiply by $b$ : $p b x + ab y = b$ . Since $p ∣ p b x$ and $p ∣ ab$ (so $p ∣ ab y$ ), $p$ divides the left side, hence $p ∣ b$ .
Extending to products. By induction, if $p ∣ q_{1} q_{2} \dots q_{m}$ , then $p ∣ q_{j}$ for some $j$ .
Uniqueness. Suppose $n = p_{1} \dots p_{r} = q_{1} \dots q_{s}$ are two prime factorizations. Then $p_{1} ∣ q_{1} \dots q_{s}$ , so by step 3 $p_{1} = q_{j}$ for some $j$ (both prime). Cancel them.
Repeat. Each $p_{i}$ matches a unique $q_{j}$ and vice versa, so $r = s$ and the multisets of primes coincide. $■$

Euler's Theorem via Group Theory

Let $U (n) = (Z / n Z)^{\times}$ be the set of residue classes coprime to $n$ . It is a group under multiplication mod $n$ with $∣ U (n) ∣ = φ (n)$ .
Closure holds because $g cd (a, n) = g cd (b, n) = 1 \Rightarrow g cd (ab, n) = 1$ ; inverses exist by Bézout (eq. [3]).
By Lagrange's Theorem, the order of any element $a \in U (n)$ divides $∣ U (n) ∣ = φ (n)$ .
Hence $a^{φ (n)} = (a^{ord (a)})^{k} \equiv 1 (mod n)$ . Taking $n = p$ gives $φ (p) = p - 1$ , recovering Fermat's Little Theorem. $■$

Carl Friedrich Gauss | 1777–1855

Gauss called number theory "the Queen of Mathematics." At age 24 he published Disquisitiones Arithmeticae (1801), which systematized congruences, introduced the now-standard $\equiv$ notation, and gave the first complete proof of quadratic reciprocity — a theorem he proved in at least eight distinct ways over his life, calling it the theorema aureum (golden theorem). He also conjectured the Prime Number Theorem as a teenager by examining prime-counting tables, anticipating the logarithmic integral $Li (x)$ as a far better approximation to $π (x)$ than $x / ln x$ . His work on Gaussian integers $Z [i]$ launched algebraic number theory.

Building Intuition

Think of the primes as a basis for the integers under multiplication — not a vector-space basis, but an analogous "independent generating set." Every integer is a unique "word" spelled in prime letters (eq. [1]). Divisibility becomes a coordinate-wise comparison: $a ∣ b$ iff every prime appears in $a$ to a lower-or-equal power than in $b$ . This is why $g cd$ and $lcm$ are just the coordinate-wise min and max of exponents.

Congruence is the act of folding the number line into a circle of circumference $n$ . Once folded, only finitely many points remain, so any question — "is there a solution?", "what are all the squares?" — becomes a finite check. The miracle of number theory is that statements about the infinite integers (eq. [4], [5]) reduce to finite combinatorics in these clocks, while the distribution of primes (eq. [6]) reaches back out to the infinite via complex analysis.

The number line folded modulo 7 into a residue clock, with quadratic residues highlighted

Worked Examples

Solving a Linear Congruence with the Extended Euclidean Algorithm

Given: Solve

17 x \equiv 5 (mod 43)

. Step 1 — Find $g cd (17, 43)$ and Bézout coefficients.

$43 = 2 \cdot 17 + 9$
$17 = 1 \cdot 9 + 8$
$9 = 1 \cdot 8 + 1$
$8 = 8 \cdot 1 + 0$ , so $g cd = 1$ (the congruence is solvable).

Step 2 — Back-substitute for $1 = 17 x + 43 y$ .

1 = 9 - 8 = 9 - (17 - 9) = 2 \cdot 9 - 17 = 2 (43 - 2 \cdot 17) - 17 = 2 \cdot 43 - 5 \cdot 17

. So

- 5 \cdot 17 \equiv 1 (mod 43)

, giving

1 7^{- 1} \equiv - 5 \equiv 38 (mod 43)

. Step 3 — Multiply both sides by the inverse.

x \equiv 38 \cdot 5 = 190 (mod 43)

. Since

190 = 4 \cdot 43 + 18

x \equiv 18 (mod 43)

Check:

17 \cdot 18 = 306 = 7 \cdot 43 + 5 \equiv 5

. ✓

Using the Chinese Remainder Theorem

Given: Find

x

with

x \equiv 2 (mod 3)

x \equiv 3 (mod 5)

x \equiv 2 (mod 7)

. Step 1 — Modulus product.

N = 3 \cdot 5 \cdot 7 = 105

. Partial products:

N_{1} = 35, N_{2} = 21, N_{3} = 15

. Step 2 — Inverses.

$35 \equiv 2 (mod 3)$ , need $2 y_{1} \equiv 1$ : $y_{1} = 2$ .
$21 \equiv 1 (mod 5)$ , so $y_{2} = 1$ .
$15 \equiv 1 (mod 7)$ , so $y_{3} = 1$ .

Step 3 — Combine.

x \equiv 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 = 140 + 63 + 30 = 233 (mod 105)

233 = 2 \cdot 105 + 23

x \equiv 23 (mod 105)

Check:

23 = 7 \cdot 3 + 2

✓,

23 = 4 \cdot 5 + 3

✓,

23 = 3 \cdot 7 + 2

✓.

Common Misconceptions

"Every ring of integers has unique factorization." False. In

Z [- 5]

6 = 2 \cdot 3 = (1 + - 5) (1 - - 5),

two genuinely different factorizations into irreducibles. The Fundamental Theorem of Arithmetic is a special property of

Z

(and of certain rings called UFDs). Recovering unique factorization in general required Dedekind's theory of ideals — and that historical failure is precisely why algebraic number theory exists. "Fermat's Little Theorem characterizes primes." Not quite. There are Carmichael numbers (e.g.,

561 = 3 \cdot 11 \cdot 17

) that are composite yet satisfy

a^{n - 1} \equiv 1 (mod n)

for all

a

coprime to

n

, fooling naive primality tests. Claim: "If

p

is prime then

2^{p} - 1

is prime (Mersenne primes)." Refutation:

p = 11

is prime, but

2^{11} - 1 = 2047 = 23 \cdot 89

is composite. Primality of the exponent is necessary (if

n

is composite,

2^{n} - 1

is composite) but not sufficient. Whether infinitely many Mersenne primes exist remains open.

Connections

Number theory sits at a crossroads. Modular arithmetic is the entry point to Abstract Algebra: $Z / n Z$ is the canonical example of a ring, and $U (n)$ a finite abelian group, so Group Theory (Lagrange's theorem) directly yields Euler's theorem (eq. [4]). The leap to analytic number theory ties the integers to Complex Analysis through the Riemann zeta function and the Euler product, which is how the Prime Number Theorem (eq. [6]) is proved. The failure of unique factorization links to Ring Theory and Dedekind domains, while Galois Theory explains quadratic reciprocity (eq. [5]) as a shadow of class field theory. Finally, the geometry of solutions to Diophantine equations connects to Elliptic Curves and Algebraic Geometry.

Real-World Applications

RSA encryption. Public-key cryptography rests on Euler's theorem (eq. [4]): encryption/decryption exponents satisfy $e d \equiv 1 (mod φ (n))$ , and security rests on the difficulty of factoring $n = pq$ (eq. [1]).
Diffie–Hellman key exchange & elliptic-curve cryptography (ECC). Security depends on the discrete logarithm problem in $U (p)$ and on elliptic curves over finite fields — used in TLS, SSH, and cryptocurrencies (Bitcoin's secp256k1).
Error-correcting codes. Reed–Solomon and BCH codes (CDs, DVDs, QR codes, deep-space probes) are built over finite fields $F_{p^{k}}$ , generalizations of $Z / p Z$ .
Hash tables and pseudorandom generators. Modular reduction $h (k) = k mod n$ and linear congruential generators $x_{n + 1} = (a x_{n} + c) mod m$ rely on congruence arithmetic (eq. [2]).
Check digits. ISBN-13, IBAN, and credit-card (Luhn) validation use modular weighted sums to detect transcription errors.
Fast computation. The Chinese Remainder Theorem speeds up RSA decryption (~4×) and underlies multi-modular arithmetic in computer algebra systems.
Primality testing. Miller–Rabin (probabilistic) and AKS (deterministic, polynomial-time) tests, foundational to generating cryptographic keys, are pure applications of Fermat-type congruences.

Historical Development

~300 BCE — Euclid. Elements Books VII–IX: the Euclidean algorithm, Euclid's Lemma, infinitude of primes, and perfect numbers.
~250 CE — Diophantus. Arithmetica studies rational/integer solutions of polynomial equations, the namesake of Diophantine analysis.
1640 — Fermat. States his "little theorem" and Fermat's Last Theorem in marginal notes; pioneers the method of infinite descent.
1736–1770 — Euler. Proves Fermat's Little Theorem, introduces the totient $φ$ , the zeta function as an Euler product, and proves $n = 4$ and $n = 3$ cases of FLT.
1801 — Gauss. Disquisitiones Arithmeticae: congruence notation, quadratic reciprocity (eq. [5]), Gaussian integers, composition of forms.
1837 — Dirichlet. Proves infinitely many primes in any arithmetic progression $a, a + d, a + 2 d, \dots$ with $g cd (a, d) = 1$ , founding analytic number theory via $L$ -functions.
1859 — Riemann. On the Number of Primes Less Than a Given Magnitude links $π (x)$ to zeros of $ζ (s)$ ; states the Riemann Hypothesis.
1896 — Hadamard & de la Vallée Poussin. Independently prove the Prime Number Theorem (eq. [6]).
1994 — Wiles (with Taylor). Proves Fermat's Last Theorem via modularity of elliptic curves, capping 350 years of effort and unifying vast areas.

Subtleties & Limits

Number theory is famous for elementary-sounding questions that resist all attack.

Riemann Hypothesis: all nontrivial zeros of $ζ (s)$ have $ℜ (s) = \frac{1}{2}$ . It would sharpen the error term in the Prime Number Theorem (eq. [6]) to $π (x) = Li (x) + O (x ln x)$ . (Clay Millennium Prize.)
Goldbach's Conjecture: every even integer $> 2$ is a sum of two primes. Verified past $4 \times 1 0^{18}$ , unproven.
Twin Prime Conjecture: infinitely many primes $p$ with $p + 2$ prime. Zhang (2013) proved bounded gaps exist; the gap is now $\leq 246$ (Polymath/Maynard), not yet $2$ .
abc Conjecture: a deep inequality relating prime factors of $a, b, a + b$ ; would imply many results including (asymptotic) FLT. Mochizuki's claimed proof remains disputed.
Infinitude of Mersenne primes and existence of odd perfect numbers — both open since antiquity.