Number Theory

Number theory is the branch of pure mathematics studying the integers and integer-valued functions. Classical results about primes and divisibility underlie modern cryptography and computer science.

1. Integers and Divisibility¶

For integers $a$ and $b$ with $b \neq 0$, we say $b$ divides $a$ (written $b \mid a$) if there exists an integer $k$ such that $a = kb$.

1.1 Division Algorithm¶

For any integers $a$ and $b > 0$, there exist unique integers $q$ (quotient) and $r$ (remainder) with $0 \leq r < b$ such that:

1.2 Greatest Common Divisor (GCD)¶

The GCD of two integers $a, b$ (not both zero) is the largest positive integer dividing both.

Euclidean algorithm — the most efficient classical method:

Least Common Multiple:

Bézout’s identity: There always exist integers $s, t$ such that

These coefficients are found by the extended Euclidean algorithm.

2. Prime Numbers¶

An integer $p > 1$ is prime if its only positive divisors are 1 and $p$ itself. Otherwise $n > 1$ is composite.

2.1 Fundamental Theorem of Arithmetic¶

Every integer $n > 1$ has a unique prime factorisation:

2.2 Density of Primes — Prime Number Theorem¶

Let $\pi(x)$ denote the number of primes $\leq x$. Then:

so primes become increasingly sparse, but there are infinitely many of them (Euclid’s proof).

2.3 Sieve of Eratosthenes¶

To find all primes up to $N$:

1. List integers $2, 3, \ldots, N$.

2. Start at $p = 2$; mark all multiples of $p$ greater than $p$ as composite.

3. Move to the next unmarked number and repeat.

4. Stop when $p > \sqrt{N}$; all unmarked numbers are prime.

2.4 Special Primes¶

3. Modular Arithmetic¶

For a positive integer $m$ (the modulus), $a \equiv b \pmod{m}$ (read “$a$ is congruent to $b$ modulo $m$”) if $m \mid (a - b)$.

Congruence behaves like equality with respect to addition and multiplication:

3.1 Residue Classes¶

The integers modulo $m$ form the set $\mathbb{Z}_m = \{0, 1, \ldots, m-1\}$ with operations defined mod $m$. $\mathbb{Z}_m$ is a field (every nonzero element has a multiplicative inverse) if and only if $m$ is prime.

3.2 Fermat’s Little Theorem¶

If $p$ is prime and $\gcd(a, p) = 1$:

Equivalently for any integer $a$: $a^p \equiv a \pmod{p}$. This is the basis of the Fermat primality test and RSA encryption.

3.3 Euler’s Theorem¶

For $\gcd(a, n) = 1$:

where $\phi(n)$ is Euler’s totient function — the count of integers in $\{1, \ldots, n\}$ coprime to $n$.

For $n = p_1^{e_1} \cdots p_k^{e_k}$:

3.4 Chinese Remainder Theorem (CRT)¶

If $m_1, m_2, \ldots, m_k$ are pairwise coprime, then for any $a_1, \ldots, a_k$ the system

has a unique solution modulo $M = m_1 m_2 \cdots m_k$.

4. Diophantine Equations¶

A Diophantine equation is a polynomial equation for which integer (or rational) solutions are sought.

4.1 Linear Diophantine Equations¶

$ax + by = c$ has integer solutions if and only if $\gcd(a, b) \mid c$. If a solution $(x_0, y_0)$ exists, the general solution is:

4.2 Pythagorean Triples¶

All positive integer solutions to $a^2 + b^2 = c^2$ (with $a < b$, $\gcd(a,b,c) = 1$) are generated by:

for integers $m > n > 0$ with $\gcd(m, n) = 1$ and $m \not\equiv n \pmod{2}$.

4.3 Pell’s Equation¶

$x^2 - Dy^2 = 1$ (where $D$ is a positive non-square integer) always has infinitely many solutions. The fundamental solution $(x_1, y_1)$ is found from the continued fraction expansion of $\sqrt{D}$.

5. Number-Theoretic Functions¶

All these functions are multiplicative: if $\gcd(a,b)=1$ then $f(ab) = f(a)f(b)$.

6. Continued Fractions¶

Any real number $x$ can be expressed as a continued fraction:

denoted $[a_0; a_1, a_2, a_3, \ldots]$, where the $a_i$ are positive integers for $i \geq 1$.

• Rational numbers have finite continued fractions.

• Quadratic irrationals (like $\sqrt{D}$) have infinite periodic continued fractions.

• Transcendental numbers like $e = [2; 1, 2, 1, 1, 4, 1, 1, 6, \ldots]$ have no periodic pattern.

The partial quotients $[a_0; a_1, \ldots, a_k] = p_k/q_k$ are called convergents and provide the best rational approximations to $x$.

7. Rational and Irrational Numbers¶

A rational number can be written as $p/q$ with $p, q \in \mathbb{Z}$, $q \neq 0$. Their decimal expansions are terminating or eventually repeating.

An irrational number cannot be expressed as a ratio of integers. Famous examples:

• $\sqrt{2}$ — proved irrational by Pythagoras; $\sqrt{p}$ is irrational for every prime $p$

• $\pi \approx 3.14159\ldots$ — also transcendental (not a root of any polynomial with integer coefficients)

• $e \approx 2.71828\ldots$ — transcendental (Hermite, 1873)

The set of real numbers is uncountable (Cantor’s diagonal argument), while the rationals are countable.

8. Cryptographic Applications¶

Number theory provides the mathematical foundation for public-key cryptography.

RSA Encryption (sketch)¶

1. Choose large primes $p, q$ and set $n = pq$.

2. Compute $\phi(n) = (p-1)(q-1)$.

3. Choose public exponent $e$ with $\gcd(e, \phi(n)) = 1$.

4. Find private exponent $d$ satisfying $ed \equiv 1 \pmod{\phi(n)}$.

5. Encrypt: $c \equiv m^e \pmod{n}$. Decrypt: $m \equiv c^d \pmod{n}$.

Security rests on the difficulty of integer factorisation of $n$ when $p$ and $q$ are large.

Diffie–Hellman Key Exchange (sketch)¶

Based on the discrete logarithm problem: given $g$, $p$ (prime), and $g^x \bmod p$, find $x$. This is believed to be computationally hard for large $p$.

9. Quadratic Residues¶

An integer $a$ is a quadratic residue modulo $p$ (odd prime, $\gcd(a,p)=1$) if the congruence $x^2 \equiv a \pmod{p}$ has a solution. Otherwise $a$ is a quadratic non-residue.

9.1 Legendre Symbol¶

Euler’s criterion:

9.2 Quadratic Reciprocity¶

For distinct odd primes $p$ and $q$:

Supplementary laws:

Quadratic reciprocity, first proved by Gauss, is often called the “golden theorem” of number theory. It allows efficient computation of the Legendre symbol.

9.3 Jacobi Symbol¶

The Jacobi symbol $\left(\frac{a}{n}\right)$ generalises the Legendre symbol to composite odd $n = p_1^{e_1}\cdots p_k^{e_k}$:

It satisfies the same reciprocity law and is efficiently computable without factoring $n$.

10. Primitive Roots and Discrete Logarithms¶

10.1 Order¶

The order of $a$ modulo $n$ (with $\gcd(a,n)=1$) is the smallest positive integer $k$ such that $a^k \equiv 1 \pmod{n}$. By Euler’s theorem, $\operatorname{ord}_n(a) \mid \phi(n)$.

10.2 Primitive Roots¶

An integer $g$ is a primitive root modulo $n$ if $\operatorname{ord}_n(g) = \phi(n)$. Primitive roots exist for $n = 1, 2, 4, p^k, 2p^k$ (where $p$ is an odd prime and $k \geq 1$).

When a primitive root $g$ exists, every integer coprime to $n$ can be written as $g^j \bmod n$ for some $j$. This is the discrete logarithm of $a$ to base $g$ modulo $n$:

10.3 Index Calculus¶

Computing discrete logarithms is believed to be hard in general. The index calculus method is the most practical attack for $\mathbb{Z}_p^*$:

1. Choose a factor base of small primes

2. Collect relations $g^{r_i} \equiv \prod p_j^{e_{ij}} \pmod{p}$

3. Solve a linear system modulo $p-1$ to find $\log_g p_j$

4. Express $\log_g a$ in terms of the factor base

11. Algebraic Integers and Gaussian Integers¶

11.1 Gaussian Integers $\mathbb{Z}[i]$¶

The ring $\mathbb{Z}[i] = \{a + bi : a, b \in \mathbb{Z}\}$ extends integer arithmetic to the complex plane.

Norm: $N(a + bi) = a^2 + b^2$. The norm is multiplicative: $N(\alpha\beta) = N(\alpha)N(\beta)$.

Units: $\pm 1, \pm i$ (elements with $N = 1$).

11.2 Primes in $\mathbb{Z}[i]$¶

A rational prime $p$ factors in $\mathbb{Z}[i]$ according to $p \bmod 4$:

Fermat’s two-square theorem: A prime $p$ is a sum of two squares ($p = a^2 + b^2$) if and only if $p = 2$ or $p \equiv 1 \pmod{4}$.

11.3 Sum of Squares¶

Lagrange’s four-square theorem: Every positive integer can be written as the sum of four squares:

12. Perfect Numbers and Mersenne Primes¶

A positive integer $n$ is perfect if $\sigma(n) = 2n$ (it equals the sum of its proper divisors).

Euclid–Euler theorem: An even number is perfect if and only if it has the form:

Known Mersenne primes correspond to $p = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, \ldots$ (52 known as of 2025).

Whether any odd perfect numbers exist is one of the oldest unsolved problems in mathematics.

13. Open Problems¶

Number theory is rich with unsolved conjectures: