Theorem sheet

Key Theorems and Formulas

The key results of the masterclass, collected unit by unit as statements and formulas. Each one is proved in its unit, with worked examples.

Number theory has a short list of results that do most of the work. Bézout's identity, the fundamental theorem of arithmetic, Fermat's little theorem in the form \(a^{p-1} \equiv 1 \pmod p\), Euler's formula for \(\varphi(n)\), the law of quadratic reciprocity, and the prime number theorem in the form \(\pi(x) \sim x/\ln x\) return in unit after unit, and a participant who can state each of them with its hypothesis has the subject in hand. This page collects those statements, in the order of the units.

Each card repeats a Key Result box of its unit: the title, the statement, and the one sentence of conditions under which it holds, such as \(\gcd(a, n) = 1\) for Euler's theorem or \(p\) an odd prime for Euler's criterion. The proof, the worked example, and the history stay in the unit, which each card links to. Named theorems appear here in their formula form; their full statements and proofs are in the Theorem and Proof boxes of the units. The page grows as units are published, so a result you cannot find yet belongs to a unit that is still to come.

The quizzes and the final exam are open book, and this page is the sheet to have open while you take them. It is also the sheet to read again before an olympiad or an examination: if a line here looks unfamiliar, the unit it names is the one to reread.

Proof, Induction, and the Integers

Binomial coefficients and Pascal’s rule

\[ \binom{n}{k} = \frac{n!}{k!\,(n-k)!} , \qquad \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \quad (1 \le k \le n - 1) \] The number of ways of choosing \(k\) objects out of \(n\). Pascal’s rule, the second formula, says that each entry of Pascal’s triangle is the sum of the two entries above it, with \(\binom{n}{0} = \binom{n}{n} = 1\) at the edges. It gives \(\binom{n}{k}\) by addition alone, without factorials.

The principle of induction

Let \(P(n)\) be a statement about the positive integer \(n\). If

  1. \(P(1)\) is true (the base case), and
  2. for every \(n \ge 1\), the truth of \(P(n)\) implies the truth of \(P(n+1)\) (the induction step),

then \(P(n)\) is true for every positive integer \(n\). In the strong form, the step may assume all of \(P(1), P(2), \ldots, P(n)\) to prove \(P(n+1)\). The base case may be any integer \(n_0\); the conclusion then holds for all \(n \ge n_0\).

Two sums worth remembering

\[ \sum_{k=1}^{n} k = \frac{n(n+1)}{2} , \qquad \sum_{k=1}^{n} (2k - 1) = n^2 \] The sum of the first \(n\) positive integers and the sum of the first \(n\) odd numbers, for every positive integer \(n\). Both are proved by induction, and both have a picture.

The well-ordering principle

Every non-empty set of positive integers has a least element. The same holds for every non-empty set of non-negative integers, and for every non-empty set of integers that is bounded below.

The pigeonhole principle

If more than \(n\) objects are placed in \(n\) boxes, then some box contains at least two objects. More generally, if more than \(kn\) objects are placed in \(n\) boxes, then some box contains at least \(k + 1\) objects.

The number of digits

\[ \text{number of decimal digits of } n = \lfloor \log_{10} n \rfloor + 1 \qquad (n \ge 1) \] The digit count of a positive integer. For \(n = 10^k\) the logarithm is exactly \(k\) and the count is \(k + 1\), which is right: \(1000\) has four digits.

Divisibility and the Euclidean Algorithm

Rules of divisibility

For all integers \(a\), \(b\), \(c\), \(x\), and \(y\):

  1. if \(a \mid b\) and \(b \mid c\), then \(a \mid c\);
  2. if \(a \mid b\) and \(a \mid c\), then \(a \mid (bx + cy)\);
  3. if \(a \mid b\) and \(b \neq 0\), then \(|a| \le |b|\);
  4. if \(a \mid b\) and \(b \mid a\), then \(a = \pm b\).

Rule 2 is the one used most often. It says that a common divisor of two numbers divides every integer combination of them, that is, every number of the form \(bx + cy\) with integers \(x\) and \(y\).

Representation in base \(b\)

Let \(b \ge 2\). Every positive integer \(n\) can be written in exactly one way as \[ n = d_k b^k + d_{k-1} b^{k-1} + \cdots + d_1 b + d_0 , \qquad 0 \le d_i < b , \quad d_k \neq 0 , \] and the integers \(d_i\) are the digits of \(n\) in base \(b\), written \(n = (d_k d_{k-1} \ldots d_1 d_0)_b\).

The reduction step of Euclid’s algorithm

For integers \(a\) and \(b > 0\), \[ \gcd(a, b) = \gcd(b,\, a \bmod b) . \] The pair \((a, b)\) and the pair \((b, r)\), where \(r\) is the remainder of \(a\) on division by \(b\), have the same common divisors and therefore the same greatest one.

Euclid’s lemma in gcd form

Let \(a\), \(b\), and \(d\) be integers. If \(d \mid ab\) and \(\gcd(d, a) = 1\), then \(d \mid b\).

Greatest common divisor and least common multiple

For positive integers \(a\) and \(b\), \[ \gcd(a, b) \cdot \operatorname{lcm}(a, b) = ab . \] For arbitrary non-zero integers the right side is \(|ab|\). Every common multiple of \(a\) and \(b\) is a multiple of \(\operatorname{lcm}(a, b)\).

The equation \(ax + by = c\)

Let \(a\) and \(b\) be integers, not both 0, and let \(d = \gcd(a, b)\). The equation \(ax + by = c\) has an integer solution if and only if \(d \mid c\). If \((x_0, y_0)\) is one solution, then all solutions are given by \[ x = x_0 + \frac{b}{d}\,t , \qquad y = y_0 - \frac{a}{d}\,t , \qquad t \in \mathbb{Z} , \] and there are infinitely many of them, spaced \(b/d\) apart in \(x\) and \(a/d\) apart in \(y\).

Sylvester’s two-stamp result

Let \(a\) and \(b\) be coprime integers greater than 1. The largest integer that cannot be written as \(ax + by\) with \(x \ge 0\) and \(y \ge 0\) is \[ ab - a - b . \] For \(a = 7\) and \(b = 11\) this is \(77 - 18 = 59\); for 3 and 5 it is 7, and for 2 and 3 it is 1.

Prime Numbers and Unique Factorization

The smallest divisor is prime

\[ \text{For every integer } n > 1, \text{ the smallest divisor } d > 1 \text{ of } n \text{ is a prime.} \] In particular every integer greater than \(1\) has at least one prime factor. The statement holds for primes as well, where the smallest divisor greater than \(1\) is \(n\) itself.

A composite number has a small prime factor

\[ n \text{ composite} \quad\Longrightarrow\quad n \text{ has a prime factor } p \le \sqrt{n} \] Turned around, if no prime up to \(\sqrt{n}\) divides \(n\), then \(n\) is prime. This is the basis of trial division, the oldest primality test: divide \(n\) by \(2, 3, 5, 7, \ldots\) up to \(\sqrt{n}\) and watch for a remainder of zero.

Canonical factorization

\[ n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} , \qquad p_1 < p_2 < \cdots < p_k \text{ primes}, \quad e_i \ge 1 \] Every integer \(n > 1\) has exactly one such representation. For \(n = 1\) the product is empty. The exponent of a prime \(p\) in \(n\) is written \(v_p(n)\) (later courses call it the \(p\)-adic valuation of \(n\)), with \(v_p(n) = 0\) when \(p \nmid n\); for example \(360 = 2^{3} \cdot 3^{2} \cdot 5\) has \(v_2(360) = 3\), \(v_5(360) = 1\), and \(v_7(360) = 0\).

The number of divisors

\[ d(n) = (e_1 + 1)(e_2 + 1) \cdots (e_k + 1) \qquad \text{for } n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \] Here \(d(n)\) is the number of positive divisors of \(n\). For example \(360 = 2^{3} \cdot 3^{2} \cdot 5\) has \(4 \cdot 3 \cdot 2 = 24\) divisors. Unit 6 develops this function and its relatives.

Greatest common divisor and least common multiple from exponents

\[ v_p\bigl(\gcd(a, b)\bigr) = \min\bigl(v_p(a), v_p(b)\bigr) , \qquad v_p\bigl(\operatorname{lcm}(a, b)\bigr) = \max\bigl(v_p(a), v_p(b)\bigr) \] The rule holds for every prime \(p\), including the primes that divide only one of the numbers, where the smaller exponent is \(0\). Since \(\min(x, y) + \max(x, y) = x + y\) for any two numbers, the identity \(\gcd(a, b) \cdot \operatorname{lcm}(a, b) = ab\) of Unit 2 follows at once.

The Lucas-Lehmer test

\begin{gather*} s_0 = 4, \qquad s_{k+1} \equiv s_k^{2} - 2 \pmod{M_p}, \\ M_p = 2^{p} - 1 \text{ is prime} \quad\Longleftrightarrow\quad s_{p-2} \equiv 0 \pmod{M_p} \end{gather*} The notation \(x \equiv y \pmod{M_p}\) means that \(x\) and \(y\) leave the same remainder on division by \(M_p\); Unit 4 develops it. For an odd prime \(p\), compute the sequence \(s_k\) modulo \(M_p\), keeping only remainders, for \(p - 2\) steps. The Mersenne number \(M_p\) is prime exactly when the last remainder is \(0\). The test was devised by Édouard Lucas (1842-1891) and put into this form by Derrick Henry Lehmer (1905-1991) in 1930; its proof needs algebra beyond this unit.

Congruences and Modular Arithmetic

Congruence modulo \(n\)

\[ a \equiv b \pmod n \quad\Longleftrightarrow\quad n \mid (a - b) \quad\Longleftrightarrow\quad a \bmod n = b \bmod n \] Two integers are congruent modulo the positive integer \(n\) exactly when \(n\) divides their difference, or equivalently when they leave the same remainder on division by \(n\). Here \(a \bmod n\) denotes that remainder, the number \(r\) with \(0 \le r < n\) from the division with remainder of Unit 2.

Arithmetic with congruences

If \(a \equiv b \pmod n\) and \(c \equiv d \pmod n\), then \[ a + c \equiv b + d \pmod n, \qquad a - c \equiv b - d \pmod n, \qquad ac \equiv bd \pmod n . \] In particular \(a \equiv b \pmod n\) implies \(a^k \equiv b^k \pmod n\) for every positive integer \(k\), and more generally \(f(a) \equiv f(b) \pmod n\) for every polynomial \(f\) with integer coefficients.

The cancellation law

\[ ac \equiv bc \pmod n \quad\Longrightarrow\quad a \equiv b \pmod{\dfrac{n}{\gcd(c, n)}} \] A common factor \(c\) may be cancelled from a congruence, but the modulus is divided by the greatest common divisor of \(c\) and \(n\). When \(\gcd(c, n) = 1\) the modulus stays the same, and \(c\) may be cancelled freely.

Existence of inverses

The residue \(a\) has an inverse modulo \(n\) if and only if \(\gcd(a, n) = 1\). The inverse is then unique modulo \(n\), and it is written \(a^{-1}\).

Repeated squaring

To compute \(a^k \bmod n\):

  1. write the exponent \(k\) in binary, as a sum of distinct powers of 2;
  2. square \(a\) repeatedly, reducing modulo \(n\) after every step, to obtain \(a^2, a^4, a^8, \ldots \bmod n\);
  3. multiply together, modulo \(n\), the powers \(a^{2^j}\) for which \(2^j\) occurs in the binary expansion of \(k\).

The method needs at most twice as many multiplications as \(k\) has binary digits, one squaring and at most one further multiplication for each digit, and every intermediate number is smaller than \(n^2\), because both factors of every product have already been reduced below \(n\).

The determinant criterion

The system \(ax + by \equiv e\), \(cx + dy \equiv f \pmod n\) has exactly one solution modulo \(n\) if and only if \(\gcd(\Delta, n) = 1\), where \(\Delta = ad - bc\), and the solution is then \[ x \equiv \Delta^{-1}(de - bf), \qquad y \equiv \Delta^{-1}(af - ce) \pmod n . \] For a prime modulus \(p\) the condition reads \(p \nmid \Delta\). When \(\gcd(\Delta, n) > 1\) the system has either no solution or several, like a linear congruence whose coefficient is not invertible.

The Theorems of Fermat, Euler, and Wilson

Euler’s totient function

\[ \varphi(n) = \text{the number of integers } k \text{ with } 1 \le k \le n \text{ and } \gcd(k, n) = 1 \] For a prime \(p\), \(\varphi(p) = p - 1\), and for a prime power, \(\varphi(p^{k}) = p^{k} - p^{k-1} = p^{k-1}(p - 1)\). By Unit 4, \(\varphi(n)\) is also the number of invertible residues modulo \(n\), that is, the number of elements of \((\mathbb{Z}/n\mathbb{Z})^{\times}\). The convention \(\varphi(1) = 1\) counts \(k = 1\), since \(\gcd(1, 1) = 1\).

The product formula for \(\varphi(n)\)

\[ \varphi(n) = \prod_{i=1}^{k} p_i^{e_i - 1}(p_i - 1) = n \prod_{p \mid n}\left(1 - \frac{1}{p}\right) \qquad \text{for } n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \] The second product runs over the distinct primes dividing \(n\), each taken once whatever its exponent. In words, \(\varphi(n)\) is \(n\) reduced by the factor \(1 - 1/p\) for each prime factor \(p\).

The multiplicative order

\[ \operatorname{ord}_n(a) = \text{the least } k \ge 1 \text{ with } a^{k} \equiv 1 \pmod n \qquad (\gcd(a, n) = 1) \] For every integer \(k \ge 0\), \(a^{k} \equiv 1 \pmod n\) holds if and only if \(\operatorname{ord}_n(a) \mid k\). In particular \(\operatorname{ord}_n(a)\) divides \(\varphi(n)\), and modulo a prime \(p\) it divides \(p - 1\).

Square roots of 1 modulo a prime

\[ x^{2} \equiv 1 \pmod p \quad\Longrightarrow\quad x \equiv 1 \text{ or } x \equiv -1 \pmod p \qquad (p \text{ prime}) \] Modulo a prime, the only residues that are their own inverse are \(1\) and \(p - 1\). For a composite modulus the statement fails: \(x = 3\) satisfies \(x^{2} = 9 \equiv 1 \pmod 8\) without being \(\pm 1\) modulo \(8\).

Korselt’s criterion

\[ n \text{ is a Carmichael number} \iff n \text{ is composite and squarefree, and } (p - 1) \mid (n - 1) \text{ for every } p \mid n \] Here \(p\) runs over the primes dividing \(n\), and squarefree means that no prime divides \(n\) twice. The direction from right to left is the argument given for \(561\); the other direction is beyond this unit. Two consequences follow in a line each: a Carmichael number is odd, since an even squarefree \(n > 2\) has an odd prime factor \(p\) and the even number \(p - 1\) cannot divide the odd number \(n - 1\); and it has at least three prime factors, since for \(n = pq\) with \(p < q\) the condition \((q - 1) \mid pq - 1 = p(q - 1) + (p - 1)\) would force \(q - 1\) to divide the smaller positive number \(p - 1\), which is impossible.

The RSA cryptosystem

\begin{gather*} \text{public key } (n, e) \text{ with } n = pq, \qquad \text{private key } d \text{ with } ed \equiv 1 \pmod{\varphi(n)}, \\ c \equiv m^{e} \pmod n, \qquad m \equiv c^{d} \pmod n \end{gather*} Key generation: choose two different large primes \(p\) and \(q\), set \(n = pq\) and \(\varphi(n) = (p - 1)(q - 1)\), choose \(e\) with \(1 < e < \varphi(n)\) and \(\gcd(e, \varphi(n)) = 1\), and compute \(d\) as the inverse of \(e\) modulo \(\varphi(n)\). Encryption of a message \(m\), an integer with \(0 \le m < n\): \(c = m^{e} \bmod n\). Decryption: \(m = c^{d} \bmod n\). The pair \((n, e)\) is published; \(d\), \(p\), \(q\), and \(\varphi(n)\) are kept secret.

Arithmetic Functions and Perfect Numbers

The number and the sum of the divisors from the factorization

\[ d(n) = \prod_{i=1}^{k} (e_i + 1) , \qquad \sigma(n) = \prod_{i=1}^{k} \frac{p_i^{e_i + 1} - 1}{p_i - 1} \qquad \text{for } n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} . \] The products run over the distinct primes dividing \(n\). For a prime power alone, \(d(p^{e}) = e + 1\) and \(\sigma(p^{e}) = 1 + p + \cdots + p^{e}\); for \(n = 1\) there is no prime at all, so both products are empty, and an empty product counts as \(1\), which gives \(d(1) = \sigma(1) = 1\).

Divisor sums of multiplicative functions

\[ \text{If } f \text{ is multiplicative, then } F(n) = \sum_{d \mid n} f(d) \text{ is multiplicative.} \] The function \(F\) is called the divisor sum of \(f\). With \(f = 1\) it gives \(F = d\), and with \(f(n) = n\) it gives \(F = \sigma\), so both are multiplicative; neither is completely multiplicative, although \(1\) and \(n\) are.

Gauss’s identity

\[ \sum_{d \mid n} \varphi(d) = n \qquad \text{for every positive integer } n . \] The sum runs over all positive divisors of \(n\), including \(1\) and \(n\). For example, the divisors of \(12\) contribute \(\varphi(1) + \varphi(2) + \varphi(3) + \varphi(4) + \varphi(6) + \varphi(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12\).

The Möbius function

\begin{equation*} \mu(n) = \begin{cases} 1 & \text{if } n = 1, \\ (-1)^{k} & \text{if } n \text{ is a product of } k \text{ distinct primes}, \\ 0 & \text{if } p^{2} \mid n \text{ for some prime } p , \end{cases} \qquad\qquad \sum_{d \mid n} \mu(d) = \begin{cases} 1 & \text{if } n = 1, \\ 0 & \text{if } n > 1 . \end{cases} \end{equation*} A number with no repeated prime factor is called squarefree; \(\mu\) is zero exactly at the numbers that are not squarefree. The function is multiplicative, since for coprime squarefree \(m\) and \(n\) the number of prime factors of \(mn\) is the sum of the two counts, so that \((-1)^{j + k} = (-1)^{j}(-1)^{k}\), and a repeated prime in \(m\) or in \(n\) is repeated in \(mn\).

The average number of divisors

\[ \ln N - 1 < \frac{1}{N} \sum_{n=1}^{N} d(n) \le \ln N + 1 \qquad \text{for every } N \ge 1 . \] The average number of divisors of the integers up to \(N\) is the natural logarithm of \(N\), to within \(1\). For \(N = 10^{6}\) the average lies between \(12.8\) and \(14.8\).

A prime Mersenne number has a prime exponent

\[ 2^{ab} - 1 = \bigl(2^{a} - 1\bigr)\bigl(1 + 2^{a} + 2^{2a} + \cdots + 2^{(b-1)a}\bigr) , \qquad \text{so } 2^{n} - 1 \text{ prime} \ \Longrightarrow\ n \text{ prime} . \] If \(n = ab\) with \(1 < a < n\), the identity shows the divisor \(2^{a} - 1\) of \(2^{n} - 1\), which lies strictly between \(1\) and \(2^{n} - 1\). The converse is false: \(2^{11} - 1\) is composite although \(11\) is prime.

Diophantine Equations

Rational points on the circle \(x^2 + y^2 = 1\)

The line of slope \(t\) through \((-1, 0)\) meets the circle again at \[ (x, y) = \left( \frac{1 - t^2}{1 + t^2},\ \frac{2t}{1 + t^2} \right) , \] and this gives every rational point of the circle except \((-1, 0)\) exactly once as \(t\) runs through the rational numbers. Writing \(t = n/m\) in lowest terms gives \(x = (m^2 - n^2)/(m^2 + n^2)\) and \(y = 2mn/(m^2 + n^2)\), and clearing the common denominator gives back the triple \((m^2 - n^2, 2mn, m^2 + n^2)\) of Section 2.

The method of descent

To prove that an equation has no solution in positive integers, suppose that it has one and choose a solution in which some positive integer attached to it (a variable, or a combination of the variables) is as small as possible. Then show that this solution produces another solution with a smaller value of the same integer. The contradiction with the choice of the smallest proves that no solution exists.

Primes of the form \(4k + 3\) never divide \(y^2 + 1\)

If \(p\) is a prime with \(p \equiv 3 \pmod 4\), then \(p \nmid y^2 + 1\) for every integer \(y\). Equivalently, the congruence \(y^2 \equiv -1 \pmod p\) has no solution for such a prime. An odd number of the form \(4k + 3\) therefore never divides a number of the form \(y^2 + 1\), because it has at least one prime factor of the form \(4k + 3\).

Brahmagupta’s identity

For any integers \(a\), \(b\), \(c\), \(e\), and \(d\), \[ (a^2 - d\,b^2)(c^2 - d\,e^2) = (ac + d\,be)^2 - d\,(ae + bc)^2 . \] In particular, if \((a, b)\) and \((c, e)\) solve \(x^2 - dy^2 = 1\), then so does \((ac + dbe, ae + bc)\). The identity says that the number \(x^2 - dy^2\) attached to the expression \(x + y\sqrt{d}\) (its norm, in the language of the field) is multiplicative. This means that when two such expressions are multiplied, as in \((a + b\sqrt{d})(c + e\sqrt{d}) = (ac + dbe) + (ae + bc)\sqrt{d}\), the norm of the product is the product of the two norms; the same multiplication rule holds with \(-\sqrt{d}\) in place of \(\sqrt{d}\).

The Great Problems of Number Theory

The meaning of \(f(x) \sim g(x)\)

\[ f(x) \sim g(x) \quad\text{means}\quad \frac{f(x)}{g(x)} \to 1 \ \text{ as } x \to \infty . \] For any margin of error, say one tenth of a per cent, there is a point beyond which \(f\) and \(g\) differ by less than that margin in proportion. The relation concerns the ratio alone; the difference may grow without bound, as in \(x^{2} + x \sim x^{2}\).

The prime heuristic

\[ \text{The chance that an integer chosen near } N \text{ is prime is about } \frac{1}{\ln N} . \] The rule is a statement about averages, not about any single integer, which is either prime or not. For a random number of \(100\) digits, \(\ln N = 100 \ln 10 = 230.3\), so about one in \(230\) such numbers is prime, and among the odd ones one in \(115\); a program that wants a \(100\)-digit prime for an RSA key (Unit 5) therefore tests a few hundred random odd numbers and expects to find one.

The zeta function for real \(s > 1\)

\[ \zeta(s) = \sum_{n=1}^{\infty} n^{-s} \le \frac{1}{1 - 2^{1-s}} , \qquad \zeta(2) = \frac{\pi^{2}}{6} . \] The sum converges for every real \(s > 1\) and diverges at \(s = 1\), where it becomes the harmonic sum. The extension of \(\zeta\) to complex values of \(s\), which the prime number theorem and the Riemann hypothesis need, is beyond this masterclass.

Primitive Roots and the Structure of Residues

The order and the order of a power

\[ a^{k} \equiv 1 \pmod n \iff \operatorname{ord}_n(a) \mid k, \qquad \operatorname{ord}_n\!\left(a^{k}\right) = \frac{\operatorname{ord}_n(a)}{\gcd\!\left(k, \operatorname{ord}_n(a)\right)} \] Both statements need \(\gcd(a, n) = 1\). The order divides \(\varphi(n)\), and modulo a prime \(p\) it divides \(p - 1\). The \(d = \operatorname{ord}_n(a)\) powers \(a, a^{2}, \ldots, a^{d} \equiv 1\) are pairwise different modulo \(n\).

The rules of indices

\[ \operatorname{ind}_g(ab) \equiv \operatorname{ind}_g a + \operatorname{ind}_g b, \qquad \operatorname{ind}_g\!\left(a^{k}\right) \equiv k \operatorname{ind}_g a \pmod{p - 1} \] For a prime \(p\), a primitive root \(g\) modulo \(p\), and residues \(a\) and \(b\) not divisible by \(p\). Also \(\operatorname{ind}_g 1 = 0\) and \(\operatorname{ind}_g g = 1\), and \(a \equiv b \pmod p\) holds exactly when \(\operatorname{ind}_g a \equiv \operatorname{ind}_g b \pmod{p - 1}\).

The criterion for \(k\)-th power residues

\[ x^{k} \equiv a \pmod p \text{ is solvable} \iff a^{(p-1)/d} \equiv 1 \pmod p, \qquad d = \gcd(k, p - 1) \] For a prime \(p\) and \(p \nmid a\). When the condition holds, the congruence has exactly \(d\) solutions, and exactly \((p - 1)/d\) of the non-zero residues \(a\) are \(k\)-th powers modulo \(p\).

The period of \(1/n\)

\[ \gcd(n, 10) = 1 \quad\Longrightarrow\quad \frac{1}{n} \text{ is purely periodic with period } \operatorname{ord}_n(10) \] The period is the length of the shortest repeating block, and purely periodic means that the block starts right after the decimal point. For a prime \(p \ne 2, 5\) the period of \(1/p\) divides \(p - 1\), and it equals \(p - 1\) exactly when \(10\) is a primitive root modulo \(p\). If \(n\) has the factors \(2\) or \(5\), a non-repeating start of \(\max(v_2(n), v_5(n))\) digits (the exponents of \(2\) and of \(5\) in \(n\)) precedes the period of \(1/m\), where \(m\) is \(n\) with those factors removed; when \(m = 1\) the expansion terminates.

The Diffie-Hellman key exchange

  1. Alice and Bob agree publicly on a large prime \(p\) and a primitive root \(g\) modulo \(p\).
  2. Alice chooses a secret exponent \(a\) and sends \(A = g^{a} \bmod p\); Bob chooses a secret \(b\) and sends \(B = g^{b} \bmod p\).
  3. Alice computes \(K = B^{a} \bmod p\) and Bob computes \(K = A^{b} \bmod p\).
  4. Both now hold the same \(K = g^{ab} \bmod p\), which serves as the key of a cipher in which both sides use the same key.

The two values agree because \(B^{a} = (g^{b})^{a} = g^{ab} = (g^{a})^{b} = A^{b}\). An eavesdropper sees \(p\), \(g\), \(A\), and \(B\), and recovering \(K\) from them is believed to require computing \(a\) from \(A\) or \(b\) from \(B\).

Quadratic Residues and Quadratic Reciprocity

The Legendre symbol

\begin{align*} \left(\frac{a}{p}\right) &= \phantom{-}1 \quad \text{if } a \text{ is a quadratic residue modulo } p, \\ \left(\frac{a}{p}\right) &= -1 \quad \text{if } a \text{ is a quadratic non-residue modulo } p, \\ \left(\frac{a}{p}\right) &= \phantom{-}0 \quad \text{if } p \mid a . \end{align*} Here \(p\) is an odd prime and \(a\) any integer. The symbol depends only on the residue class of \(a\) modulo \(p\), so \(\left(\frac{a + p}{p}\right) = \left(\frac{a}{p}\right)\), and \(\left(\frac{b^{2}}{p}\right) = 1\) whenever \(p \nmid b\).

The first supplement

\[ \left(\frac{-1}{p}\right) = (-1)^{(p-1)/2} \] For an odd prime \(p\), the symbol is \(+1\) when \(p \equiv 1 \pmod 4\) and \(-1\) when \(p \equiv 3 \pmod 4\): the number \(-1\) is a square modulo \(p\) exactly when \(p\) leaves the remainder \(1\) on division by \(4\). The name “supplement” is explained in Section 4.

Square roots modulo a prime congruent to 3 modulo 4

\[ p \equiv 3 \pmod 4, \quad \left(\frac{a}{p}\right) = 1 \quad\Longrightarrow\quad x \equiv \pm\, a^{(p+1)/4} \pmod p \ \text{ solves } \ x^{2} \equiv a . \] The exponent \((p + 1)/4\) is an integer exactly when \(p \equiv 3 \pmod 4\). The two values \(\pm\, a^{(p+1)/4}\) are the only solutions, by the two-to-one count of Section 1.

The second supplement

\[ \left(\frac{2}{p}\right) = (-1)^{(p^{2}-1)/8} \] For an odd prime \(p\), the symbol is \(+1\) when \(p \equiv 1\) or \(7 \pmod 8\) and \(-1\) when \(p \equiv 3\) or \(5 \pmod 8\): the number \(2\) is a square modulo \(p\) exactly when \(p \equiv \pm 1 \pmod 8\). The exponent \((p^{2} - 1)/8\) is an integer for every odd \(p\), and only its parity matters.

The reciprocity law and its supplements in one line

\[ \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}} \left(\frac{p}{q}\right), \qquad \left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}, \qquad \left(\frac{2}{p}\right) = (-1)^{\frac{p^{2}-1}{8}} \] For distinct odd primes \(p\) and \(q\). The sign in the first formula is \(-1\) only when \(p \equiv q \equiv 3 \pmod 4\); the second is \(+1\) for \(p \equiv 1 \pmod 4\) and the third for \(p \equiv \pm 1 \pmod 8\).

The Jacobi symbol and its reciprocity law

\[ \left(\frac{a}{n}\right) = \left(\frac{a}{p_1}\right)\left(\frac{a}{p_2}\right)\cdots\left(\frac{a}{p_k}\right) \qquad \text{for odd } n = p_1 p_2 \cdots p_k \text{ (primes, repetitions allowed)} . \] For odd positive \(m\) and \(n\) with \(\gcd(m, n) = 1\), \[ \left(\frac{m}{n}\right)\left(\frac{n}{m}\right) = (-1)^{\frac{m-1}{2}\cdot\frac{n-1}{2}}, \qquad \left(\frac{-1}{n}\right) = (-1)^{\frac{n-1}{2}}, \qquad \left(\frac{2}{n}\right) = (-1)^{\frac{n^{2}-1}{8}} , \] and the symbol is multiplicative in \(a\) and in \(n\). A value \(-1\) shows that \(a\) is a non-residue modulo \(n\); a value \(+1\) does not show that \(a\) is a residue.

Sums of Squares and Quadratic Forms

Thue’s lemma

Let \(p\) be a prime and \(a\) an integer. Then there are integers \(x\) and \(y\), not both zero, with \[ |x| < \sqrt{p}, \qquad |y| < \sqrt{p}, \qquad x \equiv a y \pmod p . \] The point of the lemma is the size of \(x\) and \(y\). A congruence modulo \(p\) between arbitrary integers says little, but a congruence between integers smaller than \(\sqrt{p}\) can be turned into an equation, as the proof of Fermat’s theorem below shows.

The Brahmagupta-Fibonacci identity

For all integers \(a, b, c, d\), \[ (a^2 + b^2)(c^2 + d^2) = (ac - bd)^2 + (ad + bc)^2 = (ac + bd)^2 + (ad - bc)^2 . \] A product of two sums of two squares is a sum of two squares, usually in two ways. The identity is Brahmagupta’s identity of Unit 7, \((a^2 - db^2)(c^2 - de^2) = (ac + dbe)^2 - d\,(ae + bc)^2\), with \(-1\) in place of the parameter \(d\) of Pell’s equation. It is also the rule \(|zw| = |z|\,|w|\) for the complex numbers \(z = a + bi\) and \(w = c + di\), whose squared absolute values are \(a^2 + b^2\) and \(c^2 + d^2\).

Jacobi’s formula for \(r_2(n)\)

For every positive integer \(n\), \[ r_2(n) = 4\,\bigl(d_1(n) - d_3(n)\bigr) , \] where \(d_1(n)\) is the number of divisors of \(n\) congruent to \(1\) modulo 4 and \(d_3(n)\) the number of divisors congruent to \(3\) modulo 4. The even divisors play no part. The formula contains the theorem above, since \(r_2(n) > 0\) exactly when \(d_1(n) > d_3(n)\).

Euler’s four-square identity

For all integers \(a, b, c, d\) and \(e, f, g, h\), \begin{align*} (a^2 + b^2 + c^2 + d^2)(e^2 + f^2 + g^2 + h^2) = {} & (ae + bf + cg + dh)^2 + (af - be + ch - dg)^2 \\ & + (ag - bh - ce + df)^2 + (ah + bg - cf - de)^2 . \end{align*} A product of two sums of four squares is a sum of four squares. The identity is the multiplicativity of the norm of the quaternions, a number system with four components \(a + bi + cj + dk\) that extends the complex numbers and whose norm is \(a^2 + b^2 + c^2 + d^2\), as the Brahmagupta-Fibonacci identity is that of the complex numbers. It can be verified by expanding both sides.

The Gauss circle estimate

The number of lattice points inside the circle of radius \(R\) satisfies \(|L(R) - \pi R^2| \le \sqrt{2}\,\pi R + \pi/2\); in terms of \(N = R^2\), \[ \sum_{n \le N} r_2(n) = \pi N + E(N), \qquad |E(N)| \le \sqrt{2}\,\pi\sqrt{N} + \pi/2 + 1 . \] The extra 1 in the second bound accounts for the origin, which \(L(R)\) counts and the sum does not. The average of \(r_2(n)\) over \(n \le N\) tends to \(\pi\), and the error \(E(N)\) grows at most like \(\sqrt{N}\), that is, like the circumference of the circle.

The Distribution of the Primes

The \(O\) notation

For positive functions \(g\), the statement \(f(x) = O(g(x))\), also written \(f(x) \ll g(x)\), means that there are constants \(C\) and \(x_0\) with \[ |f(x)| \le C\,g(x) \qquad \text{for all } x \ge x_0 . \] A formula \(f(x) = h(x) + O(g(x))\) says that \(f - h\) obeys such a bound; \(O(1)\) stands for a bounded quantity. The constant \(C\) is never named and may differ from one line to the next. For example, \(\ln n! = n\ln n - n + O(\ln n)\) and \(\operatorname{li}(x) = x/\ln x + O(x/(\ln x)^{2})\).

Legendre’s formula and the central binomial coefficient

For a prime \(p\), the exponent of \(p\) in \(n!\) is \[ v_p(n!) = \sum_{k \ge 1} \left\lfloor \frac{n}{p^{k}} \right\rfloor , \qquad\text{hence}\qquad v_p\!\left(\binom{2n}{n}\right) = \sum_{k \ge 1} \left( \left\lfloor \frac{2n}{p^{k}} \right\rfloor - 2\left\lfloor \frac{n}{p^{k}} \right\rfloor \right) . \] Each summand on the right is \(0\) or \(1\), because \(\lfloor 2y \rfloor - 2\lfloor y \rfloor\) is \(0\) when the fractional part of \(y\) is below \(\tfrac12\) and \(1\) otherwise, and the summands with \(p^{k} > 2n\) vanish. So the exponent of \(p\) in \(\binom{2n}{n}\) is at most the number of powers of \(p\) up to \(2n\), that is, at most the largest \(k\) with \(p^{k} \le 2n\), which means \(p^{v_p} \le p^{k} \le 2n\).

The Chebyshev functions and the von Mangoldt function

\[ \theta(x) = \sum_{p \le x} \ln p , \qquad \psi(x) = \sum_{p^{k} \le x} \ln p = \sum_{n \le x} \Lambda(n) , \] where the von Mangoldt function is \(\Lambda(n) = \ln p\) if \(n = p^{k}\) is a power of a prime \(p\) with \(k \ge 1\), and \(\Lambda(n) = 0\) otherwise. \(\theta(x)\) is the logarithm of the product of the primes up to \(x\); \(\psi(x)\) counts prime powers as well, each with the logarithm of its prime, and it is the logarithm of \(\operatorname{lcm}(1, 2, \ldots, \lfloor x \rfloor)\), because the least common multiple contains each prime \(p\) with the highest power \(p^{k} \le x\), and \(\ln p^{k} = k\ln p\) is one \(\ln p\) for each of the \(k\) prime powers \(p, p^{2}, \ldots, p^{k}\) up to \(x\). For example, \(\theta(100) = 83.73\) and \(\psi(100) = 94.05\); the difference comes from the ten proper prime powers up to \(100\), the powers with exponent at least \(2\), which are \(4\), \(8\), \(16\), \(32\), \(64\), \(9\), \(27\), \(81\), \(25\), and \(49\).

Three forms of the prime number theorem

\[ \pi(x) = \frac{\theta(x)}{\ln x} + O\!\left(\frac{x}{(\ln x)^{2}}\right) , \qquad\text{hence}\qquad \psi(x) \sim x \iff \theta(x) \sim x \iff \pi(x) \sim \frac{x}{\ln x} . \] Whatever is proved about \(\psi\) or \(\theta\) transfers to \(\pi\) at once; a proof of the prime number theorem may therefore aim at \(\psi(x) \sim x\) or at \(\theta(x) \sim x\), and modern proofs do.

The zeta function near \(s = 1\)

For every real \(s > 1\), \[ \frac{1}{s - 1} \ <\ \zeta(s) \ <\ \frac{s}{s - 1} , \qquad\text{so}\qquad \zeta(s) \to \infty \ \text{ and } \ (s - 1)\,\zeta(s) \to 1 \quad \text{as } s \to 1^{+} . \] The lower bound holds because \(n^{-s} \ge \int_{n}^{n+1} t^{-s}\,\dd t\) for each \(n\), so the sum exceeds \(\int_{1}^{\infty} t^{-s}\,\dd t = 1/(s - 1)\); the upper bound because \(n^{-s} \le \int_{n-1}^{n} t^{-s}\,\dd t\) for \(n \ge 2\), so the sum is at most \(1 + 1/(s - 1)\). For example, \(\zeta(1.01) = 100.58\) lies between \(100\) and \(101\).

The Riemann hypothesis as an error term

The Riemann hypothesis is equivalent to \[ \pi(x) = \operatorname{li}(x) + O\!\left(\sqrt{x}\,\ln x\right) , \qquad\text{and it implies}\qquad \left| \pi(x) - \operatorname{li}(x) \right| < \frac{\sqrt{x}\,\ln x}{8\pi} \quad \text{for all } x \ge 2657 . \] The equivalence was proved by Helge von Koch (1870-1924) in 1901 and the explicit bound by Lowell Schoenfeld (1920-2002) in 1976. At \(x = 10^{10}\) the bound is \(91{,}617\), and the actual error is \(3103\); no \(x\) is known at which the error exceeds the bound, and the hypothesis is open.

The Riemann Zeta Function

Complex powers and the comparison test

For a positive integer \(n\) and \(s = \sigma + it\), \[ n^{s} = e^{s\ln n} , \qquad |n^{s}| = n^{\sigma} , \qquad \arg n^{s} = t\ln n . \] A series \(\sum a_{n}\) of complex numbers converges absolutely if \(|a_{n}| \le b_{n}\) for all \(n\) and \(\sum b_{n}\) is a convergent series of real numbers. An absolutely convergent series may be reordered and multiplied out term by term.

The Euler product for complex \(s\)

For every complex \(s\) with \(\Re s > 1\), \[ \zeta(s) = \prod_{p} \frac{1}{1 - p^{-s}} \qquad\text{and}\qquad \zeta(s) \ne 0 . \] The product runs over all primes and means the limit of the products over \(p \le x\).

The continuation of \(\zeta\) to \(\sigma > 0\)

For every complex \(s\) with \(\Re s > 0\) and \(s \ne 1\), \[ \zeta(s) = \frac{s}{s - 1} - s\int_{1}^{\infty} \frac{\{x\}}{x^{s + 1}}\,\dd x , \] where \(\{x\} = x - \lfloor x\rfloor\) is the fractional part of \(x\). For \(\sigma > 1\) the right side equals the series ; for \(0 < \sigma \le 1\) it defines \(\zeta(s)\). The function has a simple pole at \(s = 1\) with residue \(1\), which means that \((s - 1)\zeta(s) \to 1\) as \(s \to 1\).

The Riemann hypothesis as an error term

If the Riemann hypothesis is true, then \[ \pi(x) = \operatorname{li}(x) + O\bigl(\sqrt{x}\,\ln x\bigr) , \qquad \operatorname{li}(x) = \int_{2}^{x}\frac{\dd t}{\ln t} , \] and conversely this error term implies the hypothesis (von Koch, 1901). The best error term proved without the hypothesis is far weaker; it does not even give \(\pi(x) = \operatorname{li}(x) + O(x^{1 - \delta})\) for any fixed \(\delta > 0\).

Robin’s criterion

The Riemann hypothesis is true if and only if \[ \sigma(n) < e^{\gamma}\,n\ln\ln n \qquad\text{for every } n > 5040 , \] where \(\sigma(n)\) is the sum of the divisors of \(n\) and \(e^{\gamma} = 1.7811\). The inequality fails for \(26\) integers between \(3\) and \(5040\), the last of them \(5040\) itself, and holds for every \(n > 5040\) that anyone has checked.

Primes in Arithmetic Progressions

The characters modulo \(q\)

There are exactly \(\varphi(q)\) characters of \((\mathbb{Z}/q\mathbb{Z})^{\times}\). They form a group under multiplication, with the principal character \(\chi_0 = 1\) as identity and \(\overline{\chi}\) as the inverse of \(\chi\). For a prime modulus \(p\) with primitive root \(g\) they are \[ \chi_k(g^{j}) = e^{2\pi i jk/(p-1)}, \qquad k = 0, 1, \ldots, p - 2 . \] A character with real values only, so that \(\chi = \overline{\chi}\) and the values are \(\pm 1\), is called a real character; all others are complex characters. Modulo an odd prime \(p\) the only real character besides \(\chi_0\) is the Legendre symbol, \(\chi(a) = \left(\frac{a}{p}\right)\).

The orthogonality relations

For a character \(\chi\) modulo \(q\) and an invertible residue \(a\), \begin{align*} \sum_{a \in G} \chi(a) &= \varphi(q) \ \text{ if } \chi = \chi_0, \qquad \text{and } 0 \text{ otherwise;} \\ \sum_{\chi} \chi(a) &= \varphi(q) \ \text{ if } a \equiv 1 \pmod q, \qquad \text{and } 0 \text{ otherwise,} \end{align*} where the second sum runs over all \(\varphi(q)\) characters. Consequently, for invertible residues \(a\) and \(n\), \[ \frac{1}{\varphi(q)} \sum_{\chi} \overline{\chi}(a)\,\chi(n) = 1 \ \text{ if } n \equiv a \pmod q, \qquad \text{and } 0 \text{ otherwise.} \] The last formula picks out one residue class: summed against any function of \(n\), it keeps the terms with \(n \equiv a\) and removes all others.

Dirichlet \(L\)-functions

For a Dirichlet character \(\chi\) modulo \(q\) and complex \(s = \sigma + it\) with \(\sigma > 1\), \[ L(s, \chi) = \sum_{n=1}^{\infty} \frac{\chi(n)}{n^{s}} = \prod_{p} \frac{1}{1 - \chi(p)\,p^{-s}} , \] where the series converges absolutely and the product runs over all primes. For the principal character, \(L(s, \chi_0) = \zeta(s) \prod_{p \mid q}(1 - p^{-s})\). For every non-principal character the series converges in the larger region \(\sigma > 0\) and defines a continuous function there, so that in particular \(L(1, \chi) = \sum_{n \ge 1} \chi(n)/n\) is a convergent series.

Dirichlet’s class number formula

Let \(D < 0\) be the discriminant of the forms counted by \(h(D)\) in Unit 11 (\(D = -4, -3, -20, \ldots\)), let \(\chi_D\) be the real character modulo \(|D|\) attached to it, and let \(w\) be the number of integer solutions of \(x^{2} - Dy^{2} = 4\), which is \(6\) for \(D = -3\), \(4\) for \(D = -4\), and \(2\) for all other \(D < 0\). Then \[ L(1, \chi_D) = \frac{2\pi\,h(D)}{w\sqrt{|D|}} . \] Since \(h(D) \ge 1\), the value \(L(1, \chi_D)\) is positive; this is how Dirichlet knew in 1839 that it is not zero.

The difference of a progression of primes

If \(a, a + d, \ldots, a + (k - 1)d\) are \(k\) primes and all of them are larger than \(k\), then \(d\) is divisible by every prime \(p \le k\). So the difference is a multiple of the product of the primes up to \(k\), which is \(210\) for \(k = 7\) to \(10\) and \(223{,}092{,}870\) for \(k = 23\) to \(28\). The latter product is written \(23\#\), read “23 primorial”; in general \(p\#\) means the product of the primes up to \(p\).

Sieve Methods

Legendre’s identity for the sifted set

\[ S(\mathcal{A}, z) = \sum_{d \mid P(z)} \mu(d)\,|\mathcal{A}_d| . \] The sum runs over the \(2^{\pi(z)}\) squarefree divisors \(d\) of \(P(z)\), the product of the primes below \(z\), and \(\mathcal{A}_d\) is the set of members of \(\mathcal{A}\) divisible by \(d\). The identity is exact for every finite set \(\mathcal{A}\).

The Bonferroni inequalities

For every finite set \(\mathcal{A}\), every \(z\), and every integer \(k \ge 0\), \[ \sum_{\substack{d \mid P(z) \\ \omega(d) \le 2k+1}} \mu(d)\,|\mathcal{A}_d| \;\le\; S(\mathcal{A}, z) \;\le\; \sum_{\substack{d \mid P(z) \\ \omega(d) \le 2k}} \mu(d)\,|\mathcal{A}_d| , \] where \(\omega(d)\) is the number of prime factors of \(d\). If the terms with \(\omega(d) = j\) are called the \(j\)-th round of inclusion and exclusion, then keeping an even number of rounds gives an upper bound and keeping an odd number gives a lower bound.

The parity principle

A sieve that uses only the counts \(|\mathcal{A}_d|\) of the multiples of \(d\) in \(\mathcal{A}\) cannot distinguish the members of \(\mathcal{A}\) with an odd number of prime factors from those with an even number. Consequently, for a set made of primes, such a sieve gives no lower bound at all, and every upper bound it gives is at least twice the truth.

Gaps Between Primes

The average gap between primes

\[ \frac{g_1 + g_2 + \cdots + g_{N-1}}{N - 1} = \frac{p_N - 2}{N - 1} \sim \ln p_N \sim \ln N . \] Near a large number \(x\), consecutive primes are on average about \(\ln x\) apart, which means about \(14\) near a million, \(28\) near \(10^{12}\), and \(230\) near a number of \(100\) digits. The statement is about the average, and single gaps lie far on either side of it.

Arbitrarily long gaps exist

\[ n! + 2, \ n! + 3, \ \ldots, \ n! + n \quad \text{are } n - 1 \text{ consecutive composite numbers}. \] So for every \(n\) there is a gap of at least \(n\) between consecutive primes, and the gaps \(g_n\) are unbounded. The gap found this way lies near \(n!\), where the average gap is \(\ln n! \approx n \ln n\), so the construction produces gaps far below the average of their neighbourhood.

Admissible tuples

A \(k\)-tuple \(\mathcal{H} = \{h_1, \ldots, h_k\}\) is admissible when, for every prime \(p\), some residue class modulo \(p\) contains none of the \(h_i\). Only the primes \(p \le k\) need to be checked, because \(k\) numbers cannot fill more than \(k\) classes. The width of the tuple is \(h_k - h_1\), and \(H(k)\) denotes the smallest width of an admissible \(k\)-tuple: \(H(2) = 2\), \(H(3) = 6\), \(H(4) = 8\), \(H(5) = 12\), \(H(6) = 16\), \(H(7) = 20\), \(H(50) = 246\), and \(H(105) = 600\).

The level of distribution of the primes

The primes have level of distribution \(\theta\) if, for every \(A > 0\), \[ \sum_{q \le x^{\theta - \varepsilon}} \ \max_{\gcd(a, q) = 1} \Bigl| \pi(x; q, a) - \frac{\operatorname{li}(x)}{\varphi(q)} \Bigr| \ \ll \ \frac{x}{(\ln x)^{A}} \qquad \text{for every } \varepsilon > 0 , \] where \(\pi(x; q, a)\) counts the primes up to \(x\) that are congruent to \(a\) modulo \(q\) and \(\operatorname{li}(x) = \int_2^x \dd t/\ln t\). In words, the primes are shared out evenly among the progressions to all moduli \(q\) up to \(x^{\theta}\), apart from a few exceptional \(q\) whose errors are small on average. The Bombieri-Vinogradov theorem of Unit 15 (1965) states that \(\theta = \tfrac12\) is a level of distribution, and the Elliott-Halberstam conjecture (1968) states that every \(\theta < 1\) is one.