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$.

This is a placeholder for Number Theory content.