Number Theory

Number theory is the study of the integers $\mathbb{Z}$ and their generalisations — divisibility, primes, congruences, Diophantine equations, algebraic integers, and the deep arithmetic of rational points on varieties. It is the oldest branch of pure mathematics (Euclid’s Elements, c. 300 BC, proved the infinitude of primes and the fundamental theorem of arithmetic) and the source of some of the most consequential modern results: Andrew Wiles’s 1995 proof of Fermat’s Last Theorem, the prime number theorem (Hadamard / de la Vallée Poussin 1896), the proofs of the Weil conjectures (Deligne 1974), and the partial results toward the Langlands program. It is also the source of practically every cryptographic primitive deployed at scale — RSA, elliptic-curve cryptography, lattice-based post-quantum schemes, isogeny-based protocols — and so connects deep abstract mathematics to the most quotidian engineering. This note covers divisibility and the Euclidean algorithm, primes and the distribution theorems, congruences, Fermat-Euler-Wilson, multiplicative functions, Dirichlet series and $L$-functions, quadratic reciprocity, an algebraic-number-theory primer, elliptic curves, modular forms, the Wiles proof outline, and cryptographic applications.

See also

• algebraic-geometry-foundations — schemes over $\mathbb{Z}$ and $\text{Spec }{\mathcal{O}}_K$ are the natural objects of arithmetic geometry.
• complex-analysis — the Riemann zeta function and analytic methods rely heavily on complex analysis.
• linear-algebra-essentials — modules and lattice algorithms underlie algebraic number theory and lattice-based crypto.
• information-theory — coding theory uses finite-field arithmetic and algebraic-geometric codes.
• combinatorial-optimization — integer programming and lattice reductions.
• graph-theory — expander graphs from ${\text{SL}}_2({\mathbb{F}}_p)$; Ramanujan graphs.
• probability-fundamentals — probabilistic primality tests; analytic prime distribution.
• _index — cryptography in practice (RSA, ECC, post-quantum).

1. Divisibility and the Euclidean algorithm

1.1 Divisibility

For $a,b\in \mathbb{Z}$ with $b\ne 0$, $b\mid a$ ($b$ divides $a$) means $a=bk$ for some $k\in \mathbb{Z}$. The divisibility relation is reflexive, transitive, and antisymmetric on ${\mathbb{Z}}_{\ge 1}$.

1.2 Greatest common divisor

For $a,b\in \mathbb{Z}$ not both zero, $\gcd (a,b)$ is the largest positive integer dividing both. By convention $\gcd (0,0)=0$, $\gcd (a,0)=|a|$.

Bézout’s identity (Étienne Bézout 1779): there exist $x,y\in \mathbb{Z}$ with $ax+by=\gcd (a,b)$. The coefficients are not unique but the gcd is.

1.3 Euclidean algorithm

Euclid c. 300 BC. Compute $\gcd (a,b)$ by iteration: $a=b{q}_1+r_1,b=r_1{q}_2+r_2,r_1=r_2{q}_3+r_3,\dots$ with each $r_i<r_{i-1}$. The last nonzero remainder is $\gcd (a,b)$. Reverses to give Bézout coefficients via back-substitution.

Complexity: at most $O(\log \min (a,b))$ iterations (Gabriel Lamé 1844 showed the worst case is consecutive Fibonacci numbers). Each iteration costs $O({\log }^2\max (a,b))$ bit operations naively, or $O(M(n))$ with fast multiplication. Total: $O(n^2)$ bit operations on $n$-bit inputs, improvable to $O(n{\log }^{2}n\log \log n)$ via Schönhage’s half-gcd.

1.4 Least common multiple

$\text{lcm}(a,b)=|ab|/\gcd (a,b)$.

2. Primes and the fundamental theorem

2.1 Primes

A prime is an integer $p\ge 2$ whose only positive divisors are $1$ and $p$. Smallest primes: $2,3,5,7,11,13,17,19,23,29,\dots$.

Euclid’s theorem: there are infinitely many primes. Proof: given primes $p_1,\dots ,p_n$, the number $N=p_1\cdots p_n+1$ is either prime or has a prime factor not among the $p_i$. Either way we get a new prime.

2.2 Fundamental theorem of arithmetic

Every integer $n\ge 2$ factors uniquely (up to order) as a product of primes: $n=p_1^{a_1}{p}_2^{a_2}\cdots p_k^{a_k}.$ Existence is straightforward by induction. Uniqueness uses Euclid’s lemma: if $p$ is prime and $p\mid ab$, then $p\mid a$ or $p\mid b$.

2.3 Mersenne, Fermat, and other special primes

• Mersenne primes: $M_p=2^p-1$ prime, $p$ prime. As of 2024, 52 known; the largest known prime is a Mersenne prime ($M_{82589933}$ found 2018). Conjecturally infinitely many.
• Fermat primes: $F_n=2^{2^n}+1$. Only $F_0=3,F_1=5,F_2=17,F_3=257,F_4=65537$ known to be prime; $F_5=4294967297=641\cdot 6700417$ (Euler 1732).
• Twin primes: pairs $(p,p+2)$. Conjecturally infinitely many (Polignac 1849). Yitang Zhang 2013 Annals of Math 179: there are infinitely many prime pairs differing by at most $70\times 10^6$. The Polymath8 project + James Maynard reduced this to 246.
• Sophie Germain primes: $p$ such that $2p+1$ is also prime.

3. Prime distribution

3.1 Prime counting function

$\pi (x)$ = number of primes $\le x$. Sample values: $\pi (10)=4$, $\pi (100)=25$, $\pi (10^6)=78498$, $\pi (10^{10})=455052511$.

3.2 Prime number theorem

Conjectured by Gauss (age 14, 1792) and Legendre (1798); proven independently by Jacques Hadamard 1896 and Charles-Jean de la Vallée Poussin 1896: $\pi (x)\sim \frac{x}{\log x},x\to \infty .$

Equivalently $\pi (x)\sim \text{Li}(x)={\int }_2^{x}dt/\log t$. The error term is best-stated using the latter: $\pi (x)=\text{Li}(x)+O(x{e}^{-c\sqrt{\log x}})$ unconditionally (de la Vallée Poussin), and $\pi (x)=\text{Li}(x)+O(\sqrt{x}\log x)$ under the Riemann hypothesis (Helge von Koch 1901).

3.3 The Riemann hypothesis

Riemann 1859 conjectured that all non-trivial zeros of $\zeta (s)$ have real part $1/2$. Equivalent: $\pi (x)-\text{Li}(x)=O(\sqrt{x}\log x)$. Eighth Hilbert problem (1900), first Clay Millennium Prize problem. Verified for the first $10^{13}$ zeros (van de Lune et al. and successors); widely believed.

3.4 Other distribution results

• Chebyshev (1852): $0.92\cdot x/\log x<\pi (x)<1.11\cdot x/\log x$.
• Bertrand’s postulate (Chebyshev 1850, conjectured Bertrand 1845): for every $n\ge 1$ there is a prime in $(n,2n)$.
• Dirichlet’s theorem on primes in APs (Peter Gustav Lejeune Dirichlet 1837): for $\gcd (a,q)=1$, there are infinitely many primes $\equiv a(\mathrm{mod}q)$, distributed equally among residue classes coprime to $q$: $\pi (x;q,a)\sim \frac{1}{\phi (q)}\cdot \frac{x}{\log x}.$
• Green-Tao theorem (Ben Green and Terence Tao 2008 Annals of Math 167): the primes contain arbitrarily long arithmetic progressions.

4. Congruences

4.1 Definition

$a\equiv b(\mathrm{mod}n)$ means $n\mid (a-b)$. The relation is an equivalence relation; the quotient $\mathbb{Z}/n\mathbb{Z}$ is a finite commutative ring of order $n$. The multiplicative group of units is $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }=\{a:\gcd (a,n)=1\mathrm{mod}n\}$, of order $\phi (n)$.

4.2 Chinese Remainder Theorem

Sun Tzu c. 4th century AD (in special cases); general statement clear by the 13th century. For pairwise coprime $n_1,\dots ,n_k$: $\mathbb{Z}/(n_1\cdots n_k)\mathbb{Z}\cong \mathbb{Z}/n_1\mathbb{Z}\times \cdots \times \mathbb{Z}/n_k\mathbb{Z}$ via $a\mapsto (a\mathrm{mod}{n}_1,\dots ,a\mathrm{mod}{n}_k)$. The system $x\equiv a_i(\mathrm{mod}{n}_i)$ has a unique solution mod $\prod n_i$.

Algorithmic version: use Bézout coefficients of $n_i$ and $N/n_i$ to construct the explicit solution.

4.3 Fermat’s little theorem

Pierre de Fermat 1640 (no proof); first proof by Euler 1736. For prime $p$ and $a\in \mathbb{Z}$ with $p\nmid a$: $a^{p-1}\equiv 1(\mathrm{mod}p).$ Equivalently $a^p\equiv a(\mathrm{mod}p)$ for all $a$.

4.4 Euler’s theorem

Leonhard Euler 1763. For $\gcd (a,n)=1$: $a^{\phi (n)}\equiv 1(\mathrm{mod}n).$ Generalises Fermat’s little theorem (case $n=p$). The Euler totient $\phi (n)=|\{1\le k\le n:\gcd (k,n)=1\}|$.

4.5 Wilson’s theorem

John Wilson 1770 (conjecture), Lagrange 1771 (proof). For prime $p$: $(p-1)!\equiv -1(\mathrm{mod}p).$ Converse holds: this is a primality test. Computationally inefficient ($O(p)$ vs $O((\log p{)}^c)$ for AKS) but theoretically elegant.

4.6 Order of an element

The order of $a\in (\mathbb{Z}/n\mathbb{Z}{)}^{\times }$ is the smallest $k\ge 1$ with $a^k\equiv 1(\mathrm{mod}n)$. Divides $\phi (n)$. For prime $p$, $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$ is cyclic of order $p-1$ (Gauss); a generator is a primitive root mod $p$.

5. Multiplicative functions

5.1 Definitions

$f:{\mathbb{Z}}_{\ge 1}\to \mathbb{C}$ is multiplicative if $f(mn)=f(m)f(n)$ whenever $\gcd (m,n)=1$. Completely multiplicative if the condition holds for all $m,n$.

5.2 Key examples

• $1(n)=1$ for all $n$.
• $n^s$ for any complex $s$.
• $\phi (n)=n{\prod }_{p\mid n}(1-1/p)$ — Euler’s totient.
• ${\sigma }_k(n)={\sum }_{d\mid n}{d}^k$. Special cases: ${\sigma }_0=d$ (number of divisors), ${\sigma }_1=\sigma$ (sum of divisors).
• $\mu (n)$ — Möbius function: $\mu (1)=1$, $\mu (n)=(-1{)}^k$ if $n$ is a product of $k$ distinct primes, $\mu (n)=0$ if $n$ has a squared prime factor.
• $\Lambda (n)$ — von Mangoldt function (not multiplicative): $\Lambda (p^k)=\log p$, $\Lambda (n)=0$ otherwise.

5.3 Dirichlet convolution

For arithmetic functions $f,g$: $(f\ast g)(n)={\sum }_{d\mid n}f(d)g(n/d).$ This is associative and commutative, with identity $\epsilon (n)=[n=1]$. The space of arithmetic functions with Dirichlet convolution is a commutative ring; multiplicative functions form a subgroup under convolution.

5.4 Möbius inversion

August Ferdinand Möbius 1832. If $g=1\ast f$ (i.e., $g(n)={\sum }_{d\mid n}f(d)$), then $f=\mu \ast g$ (i.e., $f(n)={\sum }_{d\mid n}\mu (d)g(n/d)$). Equivalently $\mu =1^{-1}$ in the Dirichlet convolution ring.

Examples:

• ${\sum }_{d\mid n}\phi (d)=n$, so $\phi =\mu \ast \text{Id}$.
• ${\sum }_{d\mid n}\mu (d)=[n=1]$.
• ${\sum }_{d\mid n}\Lambda (d)=\log n$.

6. Dirichlet series and $L$-functions

6.1 Dirichlet series

For an arithmetic function $f$: $D(f,s)={\sum }_{n=1}^{\infty }\frac{f(n)}{n^s}.$ Converges absolutely in a right half-plane $\text{Re}(s)>{\sigma }_a$ for some ${\sigma }_a\in [-\infty ,\infty ]$.

Convolution becomes multiplication: $D(f\ast g,s)=D(f,s)D(g,s)$.

6.2 Riemann zeta function

$\zeta (s)=D(1,s)=\sum 1/n^s$. Euler product (1737): $\zeta (s)={\prod }_p(1-p^{-s}{)}^{-1},\text{Re}(s)>1.$ This is the analytic translation of unique factorisation.

See complex-analysis for analytic continuation, functional equation, and the Riemann hypothesis.

6.3 Dirichlet $L$-functions

For a Dirichlet character $\chi :(\mathbb{Z}/q\mathbb{Z}{)}^{\times }\to {\mathbb{C}}^{\times }$ (extended by zero): $L(s,\chi )={\sum }_{n=1}^{\infty }\frac{\chi (n)}{n^s}={\prod }_p\frac{1}{1-\chi (p)p^{-s}},\text{Re}(s)>1.$

Non-trivial $L(s,\chi )$ extends analytically to $\mathbb{C}$ (entire if $\chi$ is non-principal). Non-vanishing at $s=1$ is equivalent to Dirichlet’s theorem on primes in APs. Generalised Riemann hypothesis (GRH): all non-trivial zeros lie on $\text{Re}(s)=1/2$.

6.4 Dedekind zeta function

For a number field $K$: ${\zeta }_K(s)={\sum }_{\mathfrak{a}}\frac{1}{N(\mathfrak{a}{)}^s}={\prod }_{\mathfrak{p}}\frac{1}{1-N(\mathfrak{p}{)}^{-s}}$ summing over nonzero ideals and primes of ${\mathcal{O}}_K$. Generalises $\zeta ={\zeta }_{\mathbb{Q}}$. Class number formula relates the residue at $s=1$ to the class number, regulator, discriminant, and unit group of $K$.

6.5 The Selberg class and the Langlands program

Atle Selberg 1992 axiomatised the class of “nice” $L$-functions (functional equation, analytic continuation, Euler product, Ramanujan-Petersson bound). The Langlands program (Robert Langlands 1967 letter to Weil) predicts a vast unification: $L$-functions of automorphic representations of ${\text{GL}}_n({\mathbb{A}}_K)$ correspond to $L$-functions of $n$-dimensional Galois representations. Many cases are now theorems (Wiles for ${\text{GL}}_2/\mathbb{Q}$, much of ${\text{GL}}_n$ in the function-field case via Drinfeld-Lafforgue, recent advances by Fargues-Scholze 2024).

7. Quadratic reciprocity

7.1 Legendre symbol

For odd prime $p$ and $a\in \mathbb{Z}$ with $p\nmid a$: $\left(\frac{a}{p}\right)=\{\begin{array}{ll}+1& \text{if }a\text{ is a QR mod }p,\\ -1& \text{if }a\text{ is a QNR mod }p.\end{array}$ Euler’s criterion: $\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}(\mathrm{mod}p)$.

7.2 Quadratic reciprocity

Conjectured Euler-Legendre 18th century; first proof Gauss 1796 (age 19). Gauss produced 8 distinct proofs; over 240 published proofs now exist.

For distinct odd primes $p,q$: $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1{)}^{\frac{p-1}{2}\cdot \frac{q-1}{2}}.$ Supplements: $\left(\frac{-1}{p}\right)=(-1{)}^{(p-1)/2}$ and $\left(\frac{2}{p}\right)=(-1{)}^{(p^2-1)/8}$.

7.3 Jacobi symbol

Extends Legendre to all odd $n$: $\left(\frac{a}{n}\right)={\prod }_i{\left(\frac{a}{p_i}\right)}^{e_i}$ for $n=\prod p_i^{e_i}$. Reciprocity extends. Computable in $O({\log }^{2}n)$ without factoring — central in primality testing (Solovay-Strassen).

7.4 Higher reciprocity

Cubic reciprocity (Gauss / Eisenstein), biquadratic reciprocity, and the general statement subsumed by class field theory (Takagi 1920, Artin 1927): the abelian extensions of a number field are classified by ideal class groups / idele class groups. Quadratic reciprocity emerges as the case of quadratic extensions of $\mathbb{Q}$ and the Artin reciprocity isomorphism. Modern non-abelian generalisation: the Langlands program.

8. Algebraic number theory primer

8.1 Algebraic integers and number fields

A number field $K$ is a finite-degree field extension of $\mathbb{Q}$. The ring of integers ${\mathcal{O}}_K$ is the set of $\alpha \in K$ satisfying a monic polynomial in $\mathbb{Z}[x]$.

Examples:

• $K=\mathbb{Q}$: ${\mathcal{O}}_K=\mathbb{Z}$.
• $K=\mathbb{Q}(i)$: ${\mathcal{O}}_K=\mathbb{Z}[i]$ (Gaussian integers).
• $K=\mathbb{Q}(\sqrt{2})$: ${\mathcal{O}}_K=\mathbb{Z}[\sqrt{2}]$.
• $K=\mathbb{Q}(\sqrt{-5})$: ${\mathcal{O}}_K=\mathbb{Z}[\sqrt{-5}]$. Not a UFD: $6=2\cdot 3=(1+\sqrt{-5})(1-\sqrt{-5})$.
• $K=\mathbb{Q}(\omega )$ with $\omega =e^{2\pi i/n}$: ${\mathcal{O}}_K=\mathbb{Z}[\omega ]$ — cyclotomic field.

8.2 Failure of unique factorisation; ideals

The Gaussian integers $\mathbb{Z}[i]$ are a UFD (Gauss). But many ${\mathcal{O}}_K$ are not — the example above with $\mathbb{Z}[\sqrt{-5}]$ failed Kummer’s attempts to prove FLT. Ernst Eduard Kummer’s insight (1847): factor ideals instead of elements. In ${\mathcal{O}}_K$ every nonzero ideal factors uniquely as a product of prime ideals — a Dedekind domain.

8.3 Class group

The ideal class group $\text{Cl}(K)=I(K)/P(K)$, where $I(K)$ is the group of fractional ideals and $P(K)$ the principal fractional ideals, is a finite abelian group. The class number $h_K=|\text{Cl}(K)|$ measures the failure of unique factorisation of elements.

• $h_K=1$ iff ${\mathcal{O}}_K$ is a PID iff UFD.
• For $K=\mathbb{Q}(\sqrt{-d})$ with $d>0$ squarefree: $h_K=1$ for exactly nine values $d\in \{1,2,3,7,11,19,43,67,163\}$ (Heegner 1952, Stark-Baker 1966).
• Gauss class number problem for real quadratic fields ($K=\mathbb{Q}(\sqrt{d})$, $d>0$) — conjectured infinitely many with $h=1$; still open.

8.4 Units

${\mathcal{O}}_K^{\times }$ is described by Dirichlet’s unit theorem (Dirichlet 1846): ${\mathcal{O}}_K^{\times }\cong \mu (K)\times {\mathbb{Z}}^{r_1+r_2-1}$ where $\mu (K)$ is the group of roots of unity in $K$ (finite), $r_1$ = number of real embeddings, $r_2$ = number of conjugate pairs of complex embeddings.

For real quadratic $K=\mathbb{Q}(\sqrt{d})$: ${\mathcal{O}}_K^{\times }\cong \{\pm 1\}\times \mathbb{Z}$, generated by $-1$ and a fundamental unit. Computing the fundamental unit is equivalent to solving Pell’s equation $x^2-d{y}^2=\pm 1$.

8.5 Splitting of primes

For a prime $p\in \mathbb{Z}$ and a number field $K$: $p{\mathcal{O}}_K={\mathfrak{p}}_1^{e_1}\cdots {\mathfrak{p}}_g^{e_g}$ with $\sum e_i{f}_i=[K:\mathbb{Q}]$ where $f_i$ is the residue degree. Behaviour types: split (all $e_i=1$, $g$ large), inert ($g=1$, $e_1=1$, $f_1=[K:\mathbb{Q}]$), ramified (some $e_i>1$).

For quadratic $K=\mathbb{Q}(\sqrt{d})$: $p$ splits, is inert, or ramifies according to the value of $\left(\frac{D_K}{p}\right)$ — Legendre/Kronecker symbol with the discriminant. Quadratic reciprocity governs the splitting.

9. Elliptic curves

9.1 Definition

An elliptic curve over a field $k$ (char $\ne 2,3$) is a smooth projective curve of genus $1$ with a marked point. Affine form: $E:y^2=x^3+ax+b,\Delta =-16(4a^3+27b^2)\ne 0.$ The smoothness condition is $\Delta \ne 0$.

9.2 Group law

The set of $k$-rational points $E(k)$ is an abelian group with the marked point $O$ (at infinity) as identity. Geometrically: $P+Q+R=O$ iff $P,Q,R$ are collinear (counted with multiplicity).

Explicit formulas (chord-tangent construction):

• $-P=-P$ has the same $x$-coordinate, negated $y$.
• For $P=(x_1,y_1),Q=(x_2,y_2)$ with $P\ne -Q$: slope $\lambda =(y_2-y_1)/(x_2-x_1)$ if $P\ne Q$, $\lambda =(3x_1^2+a)/(2y_1)$ if $P=Q$. Then $x_3={\lambda }^2-x_1-x_2$, $y_3=\lambda (x_1-x_3)-y_1$.

9.3 Mordell-Weil theorem

Louis Mordell 1922 for $E/\mathbb{Q}$, André Weil 1929 for general number fields: $E(K)\cong E(K{)}_{\text{tors}}\oplus {\mathbb{Z}}^r$ for a number field $K$. Here $E(K{)}_{\text{tors}}$ is the (finite) torsion subgroup and $r$ is the rank.

• Torsion is classified: Barry Mazur 1977 (Inventiones) for $K=\mathbb{Q}$ — only 15 possible groups. The largest is $\mathbb{Z}/12$ or $\mathbb{Z}/2\times \mathbb{Z}/8$.
• Rank: no known algorithm to compute in general. Maximum known rank for $E/\mathbb{Q}$ is $\ge 28$ (Elkies 2006). Conjecturally rank is unbounded — Bhargava-Skinner-Zhang show $E/\mathbb{Q}$ has rank $0$ or $1$ “most of the time” (in a precise sense over the family of elliptic curves ordered by height).

9.4 Birch-Swinnerton-Dyer conjecture

Bryan Birch and Peter Swinnerton-Dyer 1965, based on numerical computations on the EDSAC. Statement: for $E/\mathbb{Q}$, the rank of $E(\mathbb{Q})$ equals the order of vanishing of $L(s,E)$ at $s=1$: ${\text{ord}}_{s=1}L(s,E)=\text{rank}(E(\mathbb{Q})).$ The leading coefficient is given by a precise formula involving the Tamagawa numbers, regulator, $|E(\mathbb{Q}{)}_{\text{tors}}{|}^2$, and the Tate-Shafarevich group $\text{Sha}(E)$.

Status: known for rank $0$ and $1$ (Coates-Wiles 1977; Kolyvagin 1989, plus Gross-Zagier 1986). Open for higher ranks. Clay Millennium Prize problem.

9.5 Reduction mod $p$ and the Hasse bound

For $E/\mathbb{Q}$ and a prime $p$ of good reduction: $|E({\mathbb{F}}_p)|=p+1-a_p,|a_p|\le 2\sqrt{p}$ (Helmut Hasse 1933, proved as an analogue of the Riemann hypothesis for curves over finite fields).

The function $a_p$ governs the $L$-function: $L(s,E)={\prod }_p(1-a_p{p}^{-s}+p\cdot p^{-2s}{)}^{-1}$ for primes of good reduction, with adjusted Euler factors at bad primes.

10. Modular forms

10.1 Definition

A modular form of weight $k$ for ${\text{SL}}_2(\mathbb{Z})$ is a holomorphic function $f:\mathbb{H}\to \mathbb{C}$ (upper half-plane) with:

1. $f\left(\frac{az+b}{cz+d}\right)=(cz+d{)}^{k}f(z)$ for $\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)\in {\text{SL}}_2(\mathbb{Z})$.
2. Bounded as $\text{Im}(z)\to \infty$ (“holomorphic at the cusp”).

A cusp form additionally vanishes at the cusp.

The space $M_k$ of weight-$k$ modular forms is finite-dimensional; $\dim M_k$ is given by an explicit formula (zero unless $k$ is even non-negative).

10.2 Eisenstein series

$E_k(z)=\frac{1}{2}{\sum }_{(m,n)\ne (0,0)}(mz+n{)}^{-k},k\ge 4\text{ even}.$ Modular form of weight $k$. The space $M_k$ for ${\text{SL}}_2(\mathbb{Z})$ is spanned by products $E_4^a{E}_6^b$.

10.3 Discriminant cusp form

$\Delta (z)=(2\pi {)}^{12}\eta (z{)}^{24}=q{\prod }_{n=1}^{\infty }(1-q^n{)}^{24},q=e^{2\pi iz}.$ Weight-12 cusp form; unique up to scalar. The Fourier coefficients $\tau (n)$ are the Ramanujan tau function. Ramanujan-Petersson conjecture: $|\tau (p)|\le 2p^{11/2}$ — proved by Deligne 1974 as a consequence of the Weil conjectures.

10.4 Hecke operators

Erich Hecke 1937. Operators $T_n$ acting on modular forms. Their eigenforms have multiplicative Fourier coefficients. The simultaneous eigenforms (Hecke eigenforms) are the “atoms” — they give rise to $L$-functions: $L(s,f)={\sum }_{n=1}^{\infty }\frac{a_n}{n^s}={\prod }_p\frac{1}{1-a_p{p}^{-s}+p^{k-1}{p}^{-2s}}.$

10.5 Modularity theorem (Taniyama-Shimura-Weil)

Statement: every elliptic curve $E/\mathbb{Q}$ is modular: there is a weight-2 cusp form $f$ for ${\Gamma }_0(N)$ ($N$ = conductor of $E$) such that $L(s,E)=L(s,f)$.

Wiles 1995 Annals of Math 141 proved the semistable case (sufficient for FLT). Breuil-Conrad-Diamond-Taylor 2001 Journal of the AMS 14 completed the general case.

11. Fermat’s Last Theorem

11.1 Statement

Pierre de Fermat 1637 marginal note in his copy of Diophantus: $x^n+y^n=z^n$ has no solution in positive integers for $n\ge 3$. The note’s claim of a proof was almost certainly mistaken.

11.2 Historical attempts

• Fermat: proof for $n=4$ (infinite descent).
• Euler 1770: $n=3$ (with gap in unique factorisation, later filled).
• Dirichlet, Legendre: $n=5$.
• Lamé 1839: $n=7$ (very intricate).
• Kummer 1850s: $n$ regular prime — succeeded for many $n$ but failed at irregular primes.
• 20th century: computational verification up to $n=4\times 10^6$ (Buhler-Crandall-Sompolski 1992 and beyond).

11.3 Wiles’s proof outline

The reduction was discovered by Gerhard Frey 1986 and made precise by Ribet 1990 (epsilon conjecture).

1. Frey curve: if $a^p+b^p=c^p$ is a hypothetical solution with $p\ge 5$ prime, form the elliptic curve $E_{a,b,c}:y^2=x(x-a^p)(x+b^p)$.
2. Ribet’s theorem: $E_{a,b,c}$ would be “not modular” in a specific sense (the corresponding mod-$p$ Galois representation would not arise from a modular form of weight $2$ and the right level).
3. Modularity theorem (Wiles): every semistable $E/\mathbb{Q}$ is modular.
4. Contradiction: $E_{a,b,c}$ is semistable, hence modular, contradicting step 2.

The proof of modularity occupies hundreds of pages and uses deformation theory of Galois representations, $R=T$ theorems (Wiles, Taylor-Wiles), and a Galois-cohomological obstruction calculus. A widely accessible exposition: Cornell, Silverman, Stevens (eds.) Modular Forms and Fermat’s Last Theorem 1997.

12. Cryptography

12.1 RSA

Rivest-Shamir-Adleman 1977 (and Clifford Cocks 1973, independently at GCHQ, declassified 1997). Choose primes $p,q$, compute $n=pq$ and $\phi (n)=(p-1)(q-1)$. Pick public exponent $e$ coprime to $\phi (n)$ and private $d\equiv e^{-1}(\mathrm{mod}\phi (n))$. Public key $(n,e)$; private key $d$.

Encryption: $c=m^e\mathrm{mod}n$. Decryption: $m=c^d\mathrm{mod}n$, valid by Euler’s theorem.

Security rests on the hardness of integer factorisation. Best classical algorithm: General Number Field Sieve (Pollard 1988, Buhler-Lenstra-Pomerance 1993), subexponential complexity $\exp (((64/9{)}^{1/3}+o(1))(\log n{)}^{1/3}(\log \log n{)}^{2/3})$. Current key sizes: 2048-3072 bit for long-term security, 4096-bit for high-security.

12.2 Elliptic-curve cryptography

Neal Koblitz 1987 / Victor Miller 1985 (independent). Use $E({\mathbb{F}}_p)$ for cryptographic primitives. Discrete log problem: given $P,Q\in E({\mathbb{F}}_p)$, find $k$ with $Q=kP$.

Best generic attack: Pollard rho, $O(\sqrt{n})$ where $n=|E({\mathbb{F}}_p)|$. No subexponential attack for “generic” curves (unlike $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$).

Practical curves: P-256 (NIST), secp256k1 (Bitcoin, Ethereum), Curve25519 (Daniel Bernstein 2005, used in TLS 1.3 / Signal). 256-bit ECC gives roughly the same security as 3072-bit RSA, with much smaller keys and faster operations.

12.3 Pairing-based cryptography

Bilinear pairings on elliptic curves (Weil pairing, Tate pairing). Enable identity-based encryption (Boneh-Franklin 2001), short signatures (BLS — Boneh-Lynn-Shacham 2001), and the foundations of zk-SNARKs in many SNARK schemes (Groth16, KZG commitments). Used in Ethereum precompiles (BN254, BLS12-381).

12.4 Lattice-based post-quantum

Shor’s algorithm (Peter Shor 1994) breaks RSA and ECC on a sufficiently large quantum computer. NIST PQC standardisation 2022-2024 selected lattice-based schemes:

• CRYSTALS-Kyber (key encapsulation), based on Module-LWE.
• CRYSTALS-Dilithium (signatures), based on Module-LWE + Module-SIS.
• FALCON (signatures), based on NTRU lattices.

Hardness: Shortest Vector Problem (SVP) and Closest Vector Problem (CVP) on Euclidean lattices. Best classical algorithms: BKZ lattice reduction (Schnorr 1987, refined by Chen-Nguyen 2011), running time exponential in the lattice dimension.

12.5 Isogeny-based cryptography

Use isogenies between supersingular elliptic curves. SIDH (Jao-De Feo 2011) was broken in 2022 (Castryck-Decru attack on SIDH, using Kani’s theorem). SQISign (De Feo-Kohel-Leroux-Petit-Wesolowski 2020) survives and is a NIST round-4 alternative. CSIDH (Castryck-Lange-Martindale-Panny-Renes 2018) is a slower non-broken alternative.

12.6 Other crypto primitives from number theory

• Diffie-Hellman key exchange (1976): $g^{ab}$ from $g^a,g^b$. Multiplicative group of ${\mathbb{F}}_p^{\times }$ or elliptic curve.
• DSA / ECDSA: digital signatures.
• Schnorr signatures: simpler and provably secure; used in Bitcoin Taproot (BIP340).
• Paillier cryptosystem: additively homomorphic; foundation of older private-set-intersection protocols.
• Hash-to-curve: maps inputs to elliptic-curve points; foundational for BLS signatures, VRFs.

13. Diophantine approximation

13.1 Liouville’s theorem

For an algebraic $\alpha$ of degree $d$, there is a constant $c>0$ such that for all $p/q$ rational with $q\ge 1$: $\left|\alpha -\frac{p}{q}\right|>\frac{c}{q^d}.$ Used by Joseph Liouville 1844 to construct the first transcendental numbers (Liouville constant $\sum 10^{-n!}$).

13.2 Roth’s theorem

Klaus Roth 1955 (Fields 1958): for any algebraic irrational $\alpha$ and $\epsilon >0$, there are only finitely many $p/q$ with $\left|\alpha -\frac{p}{q}\right|<\frac{1}{q^{2+\epsilon }}.$ The exponent $2$ is best possible (Dirichlet shows $|\alpha -p/q|<1/q^2$ has infinitely many solutions for any irrational $\alpha$). Inexplicit — the constants depending on $\alpha ,\epsilon$ are not effective.

13.3 Schmidt’s subspace theorem

Wolfgang Schmidt 1972: generalises Roth to simultaneous Diophantine approximations. The far-reaching consequences include effective bounds for solutions of $S$-unit equations and norm-form equations.

13.4 Faltings’s theorem (Mordell conjecture)

Gerd Faltings 1983 Inventiones Mathematicae 73 (Fields 1986): a smooth projective curve of genus $\ge 2$ over a number field has only finitely many rational points. Conjectured by Mordell 1922. Bombieri 1990 gave a different proof; Vojta 1991 gave a third. Effective bounds remain open.

14. Computational number theory

14.1 Primality testing

• Fermat test: $a^{n-1}\equiv 1(\mathrm{mod}n)$ — necessary but not sufficient (Carmichael numbers fool it).
• Miller-Rabin (Gary Miller 1976, Michael Rabin 1980): probabilistic, $O((\log n{)}^3)$ per round, fails with probability $\le 1/4$ per round.
• Solovay-Strassen (1977): probabilistic via Jacobi symbol.
• AKS (Agrawal-Kayal-Saxena 2002 Annals of Math 160): first deterministic polynomial-time primality test. $\tilde{O}((\log n{)}^6)$, later improved to $\tilde{O}((\log n{)}^{15/2})$. Theoretical; in practice slower than Miller-Rabin.
• ECPP (Atkin 1986, Goldwasser-Kilian 1986): generates a primality certificate. Used for very large primes.

14.2 Integer factorisation

• Trial division: $O(\sqrt{n})$.
• Pollard rho (1975): $O(n^{1/4})$ expected, low memory.
• Pollard $p-1$ (1974): exploits smooth $p-1$.
• Quadratic Sieve (Pomerance 1981): subexponential.
• Number Field Sieve (Pollard 1988, GNFS 1993): subexponential $\exp (((64/9{)}^{1/3})(\log n{)}^{1/3}(\log \log n{)}^{2/3})$. Current record: RSA-250 (829 bits) factored 2020 by Boudot et al.
• Shor’s algorithm (1994): polynomial-time on a quantum computer. Largest reliable Shor factorisations to date are very small (15, 21, 35) — engineering, not theoretical, barrier.

14.3 Discrete logarithm

In ${\mathbb{F}}_p^{\times }$: index calculus, similar complexity to GNFS for factoring. In small-characteristic finite fields (${\mathbb{F}}_{2^n}$, ${\mathbb{F}}_{3^n}$): quasi-polynomial algorithms (Barbulescu-Gaudry-Joux-Thomé 2013, Eurocrypt).

In generic groups (including elliptic curves on most curves): Pollard rho, $O(\sqrt{n})$. No subexponential attack known for properly chosen elliptic curves.

14.4 Algorithmic tools

• Lenstra-Lenstra-Lovász (LLL) lattice basis reduction (Lenstra-Lenstra-Lovász 1982): polynomial-time approximation of shortest vector. Foundation of practical lattice cryptanalysis and many integer-relation algorithms.
• Coppersmith’s method (1996): finding small roots of polynomials mod $N$, leveraged in lattice attacks on RSA with small private exponent or small messages.
• PARI/GP, SageMath, Magma, Pari, FLINT — software for computational number theory.

15. Open problems

• Riemann hypothesis and the generalised RH for $L$-functions.
• Goldbach’s conjecture (1742): every even $n\ge 4$ is a sum of two primes. Vinogradov 1937 proved every sufficiently large odd $n$ is a sum of three primes; Helfgott 2013 ternary Goldbach for all odd $n\ge 7$.
• Twin prime conjecture: infinitely many $(p,p+2)$ both prime. Polymath/Maynard reduced the gap-of-bounded-difference to 246.
• abc conjecture (Oesterlé-Masser 1985): for $a+b=c$ coprime, $c{\ll }_{\epsilon }\text{rad}(abc{)}^{1+\epsilon }$. Shinichi Mochizuki’s 2012 IUT proof is widely disputed.
• Birch-Swinnerton-Dyer conjecture.
• Langlands program in full generality.
• Class number 1 problem for real quadratic fields.
• Catalan’s conjecture: $8$ and $9$ are the only consecutive perfect powers (Mihailescu 2002).
• Schanuel’s conjecture: transcendence-theoretic; implies many open transcendence results.

16. Connections to other libraries

• Algebra: number theory is a major consumer of group theory (Galois groups), ring theory (Dedekind domains), and homological algebra (group cohomology).
• Algebraic geometry: schemes over $\mathbb{Z}$, étale cohomology, arithmetic schemes; see algebraic-geometry-foundations.
• Complex analysis: $\zeta$, $L$-functions, modular forms; see complex-analysis.
• Combinatorics: additive combinatorics (Gowers, Tao); see graph-theory.
• Computer science: cryptography, complexity (factoring is in NP $\cap$ co-NP but not known P or NP-complete), pseudo-random number generation.
• Physics: quasi-crystal diffraction (Meyer sets and Pisot numbers); chaos at the critical line.

Further reading

• Hardy, G. H. and E. M. Wright (Heath-Brown, Silverman, Wiles rev.). 2008. An Introduction to the Theory of Numbers (6th ed.). Oxford.
• Ireland, K. and M. Rosen. 1990. A Classical Introduction to Modern Number Theory (2nd ed.). Springer GTM 84.
• Marcus, D. A. 2018. Number Fields (2nd ed.). Springer.
• Lang, S. 1994. Algebraic Number Theory (2nd ed.). Springer GTM 110.
• Neukirch, J. 1999. Algebraic Number Theory. Springer.
• Silverman, J. H. 2009. The Arithmetic of Elliptic Curves (2nd ed.). Springer GTM 106.
• Silverman, J. H. 1994. Advanced Topics in the Arithmetic of Elliptic Curves. Springer GTM 151.
• Diamond, F. and J. Shurman. 2005. A First Course in Modular Forms. Springer GTM 228.
• Cornell, G., J. H. Silverman, G. Stevens (eds.). 1997. Modular Forms and Fermat’s Last Theorem. Springer.
• Iwaniec, H. and E. Kowalski. 2004. Analytic Number Theory. AMS Colloquium Publications 53.
• Davenport, H. (Montgomery rev.). 2000. Multiplicative Number Theory (3rd ed.). Springer.
• Cohen, H. 1993. A Course in Computational Algebraic Number Theory. Springer.
• Stein, W. 2007. Elementary Number Theory: Primes, Congruences, and Secrets. Online.
• Tate, J. and J. Silverman. 2015. Rational Points on Elliptic Curves (2nd ed.). Springer.
• Koblitz, N. 1994. A Course in Number Theory and Cryptography (2nd ed.). Springer.
• Galbraith, S. D. 2012. Mathematics of Public Key Cryptography. Cambridge.

Adjacent

• algebraic-geometry-foundations
• complex-analysis
• linear-algebra-essentials
• information-theory
• combinatorial-optimization
• graph-theory
• probability-fundamentals
• measure-theory-and-integration