Number Theory

⚡ Key Takeaways

Number Theory is the study of the integers $\mathbb{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.

💡 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 $\mathbb{Z}/n\mathbb{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.

DefinitionDivisibility and Primes

For integers $a, b$ with $a \neq 0$ , we say $a$ divides $b$ (written $a \mid 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 $\gcd(a,b)$ is the largest positive integer dividing both $a$ and $b$ ; if $\gcd(a,b)=1$ , $a$ and $b$ are coprime.

TheoremFundamental 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:

DefinitionCongruence

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

TheoremBézout's Identity

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

TheoremFermat's Little Theorem & Euler's Theorem

If $p$ is prime and $p \nmid a$ , then $a^{p-1} \equiv 1 \pmod{p}$ . More generally, if $\gcd(a,n)=1$ ,

TheoremQuadratic Reciprocity

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

TheoremPrime Number Theorem

Letting $\pi(x)$ count primes $\le x$ ,

ProofUniqueness in the Fundamental Theorem of Arithmetic

We prove uniqueness, given existence. 1. Euclid's Lemma. Suppose $p$ is prime and $p \mid ab$ . If $p \nmid a$ , then $\gcd(p,a)=1$ (since $p$ 's only divisors are $1,p$ ). By Bézout (eq. [3]) there are integers $x,y$ with $px + ay = 1$ . 2. Multiply by $b$ : $pbx + aby = b$ . Since $p \mid pbx$ and $p \mid ab$ (so $p \mid aby$ ), $p$ divides the left side, hence $p \mid b$ . 3. Extending to products. By induction, if $p \mid q_1 q_2 \cdots q_m$ , then $p \mid q_j$ for some $j$ . 4. Uniqueness. Suppose $n = p_1\cdots p_r = q_1 \cdots q_s$ are two prime factorizations. Then $p_1 \mid q_1\cdots q_s$ , so by step 3 $p_1 = q_j$ for some $j$ (both prime). Cancel them. 5. Repeat. Each $p_i$ matches a unique $q_j$ and vice versa, so $r = s$ and the multisets of primes coincide. $\blacksquare$

∎

ProofEuler's Theorem via Group Theory

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

∎

mathematician · 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 $\mathrm{Li}(x)$ as a far better approximation to $\pi(x)$ than $x/\ln x$ . His work on Gaussian integers $\mathbb{Z}[i]$ launched algebraic number theory.

🧠 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 \mid b$ iff every prime appears in $a$ to a lower-or-equal power than in $b$ . This is why $\gcd$ and $\mathrm{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.

Figure

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

ExampleSolving a Linear Congruence with the Extended Euclidean Algorithm

Given: Solve $17x \equiv 5 \pmod{43}$ .

Step 1 — Find $\gcd(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 $\gcd = 1$ (the congruence is solvable).

Step 2 — Back-substitute for $1 = 17x + 43y$ . $1 = 9 - 8 = 9 - (17-9) = 2\cdot 9 - 17 = 2(43 - 2\cdot17) - 17 = 2\cdot43 - 5\cdot17$ . So $-5\cdot17 \equiv 1 \pmod{43}$ , giving $17^{-1} \equiv -5 \equiv 38 \pmod{43}$ .

Step 3 — Multiply both sides by the inverse. $x \equiv 38 \cdot 5 = 190 \pmod{43}$ . Since $190 = 4\cdot43 + 18$ :

\boxed{x \equiv 18 \pmod{43}}

Check: $17\cdot 18 = 306 = 7\cdot43 + 5 \equiv 5$ . ✓

ExampleUsing the Chinese Remainder Theorem

Given: Find $x$ with $x \equiv 2 \pmod 3$ , $x \equiv 3 \pmod 5$ , $x \equiv 2 \pmod 7$ .

Step 1 — Modulus product. $N = 3\cdot5\cdot7 = 105$ . Partial products: $N_1 = 35,\ N_2 = 21,\ N_3 = 15$ .

Step 2 — Inverses.

$35 \equiv 2 \pmod 3$ , need $2y_1\equiv1$ : $y_1 = 2$ .
$21 \equiv 1 \pmod 5$ , so $y_2 = 1$ .
$15 \equiv 1 \pmod 7$ , so $y_3 = 1$ .

Step 3 — Combine. $x \equiv 2\cdot35\cdot2 + 3\cdot21\cdot1 + 2\cdot15\cdot1 = 140 + 63 + 30 = 233 \pmod{105}$ . $233 = 2\cdot105 + 23$ :

\boxed{x \equiv 23 \pmod{105}}

Check: $23 = 7\cdot3+2$ ✓, $23 = 4\cdot5+3$ ✓, $23 = 3\cdot7+2$ ✓.

⚠️ Common mistake

"Every ring of integers has unique factorization." False. In $\mathbb{Z}[\sqrt{-5}]$ ,

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

two genuinely different factorizations into irreducibles. The Fundamental Theorem of Arithmetic is a special property of $\mathbb{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\cdot11\cdot17$ ) that are composite yet satisfy $a^{n-1}\equiv 1 \pmod n$ for all $a$ coprime to $n$ , fooling naive primality tests.

Counterexample

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.

connection

Number theory sits at a crossroads. Modular arithmetic is the entry point to Abstract Algebra: $\mathbb{Z}/n\mathbb{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.

🔬 Where this appears

⏳ History

- ~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

\varphi

, 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+2d,\dots

with

\gcd(a,d)=1

, founding analytic number theory via

L

-functions.

- 1859 — Riemann. On the Number of Primes Less Than a Given Magnitude links

\pi(x)

to zeros of

\zeta(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.

open-problem

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

Riemann Hypothesis: all nontrivial zeros of $\zeta(s)$ have $\Re(s) = \tfrac12$ . It would sharpen the error term in the Prime Number Theorem (eq. [6]) to $\pi(x) = \mathrm{Li}(x) + O(\sqrt{x}\ln x)$ . (Clay Millennium Prize.)
Goldbach's Conjecture: every even integer $> 2$ is a sum of two primes. Verified past $4\times10^{18}$ , unproven.
Twin Prime Conjecture: infinitely many primes $p$ with $p+2$ prime. Zhang (2013) proved bounded gaps exist; the gap is now $\le 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.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also