Primes and unique factorization

The primes are the multiplicative building blocks of the integers, as atoms are the building blocks of molecules. This lesson proves the two founding facts about them, both in Euclid: there are infinitely many primes, and every integer greater than 1 factors into primes in exactly one way. The second fact, the fundamental theorem of arithmetic, is so familiar that it is easy to think it obvious. It is not, and the lesson ends with a number system in which it fails.

Primes and composites

Definition. An integer \(p > 1\) is prime if its only positive divisors are 1 and \(p\). An integer \(n > 1\) that is not prime is composite; then \(n = ab\) with \(1 < a, b < n\). The number 1 is neither prime nor composite. The primes below 50 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. Excluding 1 from the primes is a convention, but a good one: it is exactly what makes factorization unique, since otherwise \(6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3\).

Lemma. Every integer \(n > 1\) has a prime divisor. Proof: the set of divisors of \(n\) greater than 1 is nonempty (it contains \(n\)), so it has a least element \(p\). If \(p\) were composite, \(p = ab\) with \(1 < a < p\), then \(a\) would be a smaller divisor of \(n\) greater than 1. So \(p\) is prime.

Lemma. If \(n > 1\) is composite, it has a prime divisor \(p \le \sqrt n\). Proof: write \(n = ab\) with \(1 < a \le b\). Then \(a^2 \le ab = n\), so \(a \le \sqrt n\), and any prime divisor of \(a\) will do. Consequently, to test whether \(n\) is prime it suffices to try division by the primes up to \(\sqrt n\). To show 211 is prime we only need to check 2, 3, 5, 7, 11 and 13, since \(17^2 = 289 > 211\).

The sieve of Eratosthenes

The same observation gives an efficient way to list all primes up to a bound \(N\). Write down 2, 3, …, \(N\). Circle 2 and cross out its other multiples. The next uncrossed number, 3, is prime; circle it and cross out its multiples. Continue: each time, the smallest number not yet crossed out is prime. Once the circled prime exceeds \(\sqrt N\), every number still standing is prime, because a composite number up to \(N\) has a prime factor at most \(\sqrt N\) and has therefore been crossed out.

The figure tints each composite by its smallest prime factor, the prime that first crossed it out. Observe that the multiples of 7 that survive the earlier rounds start at \(49 = 7^2\): every smaller multiple of 7 has a smaller prime factor. In general one may start crossing out multiples of \(p\) at \(p^2\). The sieve is about 2,200 years old and, with refinements, it is still the fastest way to produce all the primes in a range.

There are infinitely many primes

Theorem (Euclid). There are infinitely many primes.

Proof. Suppose \(p_1, p_2, \ldots, p_k\) is any finite list of primes. Let \(N = p_1p_2\cdots p_k + 1\). By the lemma, \(N\) has a prime divisor \(p\). If \(p\) were one of the \(p_i\), it would divide both \(N\) and \(p_1\cdots p_k\), hence their difference 1, which is impossible. So \(p\) is a prime not on the list. No finite list contains all the primes.

Note what the proof does not say: \(N\) need not be prime itself. With the first six primes, \(2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509\). The proof is constructive in a weak sense: from any list it produces a new prime, here 59.

Variations of Euclid's argument prove more. There are infinitely many primes of the form \(4k + 3\): given such primes \(p_1, \ldots, p_k\), consider \(N = 4p_1\cdots p_k - 1\). It is odd and has the form \(4k + 3\). A product of numbers of the form \(4k + 1\) is again of that form, since \((4a + 1)(4b + 1) = 4(4ab + a + b) + 1\), so \(N\) must have a prime factor of the form \(4k + 3\), and it is not any \(p_i\). Dirichlet proved in 1837 that every progression \(a, a + d, a + 2d, \ldots\) with \(\gcd(a, d) = 1\) contains infinitely many primes, but his proof needs analysis and is beyond this course.

How the primes are distributed

Primes thin out but never stop. There are arbitrarily long gaps between them: the numbers \(n! + 2, n! + 3, \ldots, n! + n\) are \(n - 1\) consecutive composites, since \(k\) divides \(n! + k\) for \(2 \le k \le n\). Yet primes also cluster: twin primes such as 11 and 13, 17 and 19, 41 and 43 seem to go on forever, but whether there are infinitely many is an open problem. In 2013 Yitang Zhang proved that some gap below 70 million occurs infinitely often, and collaborative work soon reduced the bound to 246.

Let \(\pi(x)\) be the number of primes up to \(x\). Gauss, studying tables of primes as a teenager in the 1790s, guessed that the density of primes near \(x\) is about \(1/\ln x\). The prime number theorem, proved independently by Hadamard and de la Vallée Poussin in 1896, confirms that \[\pi(x) \sim \frac{x}{\ln x},\] meaning that the ratio tends to 1 as \(x\) grows.

The figure shows the staircase \(\pi(x)\) and the smooth curve \(x/\ln x\). At \(x = 1000\) they are 168 and about 145, a ratio of 1.16; at \(x = 10^9\) the ratio is about 1.05. The error is a famous subject in its own right: the Riemann hypothesis, the most celebrated open problem in mathematics, is equivalent to a precise bound on how far \(\pi(x)\) can stray from a refined approximation.

Euclid's lemma for primes

Theorem. If a prime \(p\) divides a product \(ab\), then \(p \mid a\) or \(p \mid b\). More generally, if \(p \mid a_1a_2\cdots a_k\), then \(p\) divides some \(a_i\).

Proof. The only positive divisors of \(p\) are 1 and \(p\), so \(\gcd(p, a)\) is 1 or \(p\). If it is \(p\), then \(p \mid a\). If it is 1, Euclid's lemma from lesson 2 gives \(p \mid b\). The general case follows by induction on \(k\), applying the two-factor case to \(a_1 \cdot (a_2\cdots a_k)\).

This property characterizes primes: a composite \(n = ab\) with \(1 < a, b < n\) divides \(ab\) but neither factor. It fails for composites such as 6, which divides \(4 \cdot 9\) but neither 4 nor 9.

The fundamental theorem of arithmetic

Theorem. Every integer \(n > 1\) can be written as a product of primes, \(n = p_1p_2\cdots p_k\), and this factorization is unique apart from the order of the factors.

Proof of existence, by strong induction. If \(n\) is prime, it is a product of one prime. Otherwise \(n = ab\) with \(1 < a, b < n\), and by the induction hypothesis \(a\) and \(b\) are products of primes; putting the two products together factors \(n\).

Proof of uniqueness. Suppose \(p_1p_2\cdots p_k = q_1q_2\cdots q_l\), with all \(p_i, q_j\) prime. Then \(p_1\) divides the right side, so by Euclid's lemma \(p_1 \mid q_j\) for some \(j\). Since \(q_j\) is prime and \(p_1 > 1\), \(p_1 = q_j\). Cancel it from both sides and repeat (formally, induct on \(k\)). At the end every \(p\) has been matched with an equal \(q\), and no factors are left over on either side, since a product of primes is never 1.

Grouping equal primes gives the canonical factorization \[n = p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}, \qquad p_1 < p_2 < \cdots < p_r,\ e_i \ge 1.\] For example \(360 = 2^3 \cdot 3^2 \cdot 5\) and \(2026 = 2 \cdot 1013\). It is often convenient to allow zero exponents and write two numbers over the same primes: \(a = \prod p_i^{\alpha_i}\), \(b = \prod p_i^{\beta_i}\).

Consequences of unique factorization

With factorizations in hand, divisibility becomes a comparison of exponents. If \(n = \prod p_i^{e_i}\), then \(d\) divides \(n\) exactly when \(d = \prod p_i^{f_i}\) with \(0 \le f_i \le e_i\) for each \(i\). It follows that \[\gcd(a, b) = \prod p_i^{\min(\alpha_i, \beta_i)}, \qquad \operatorname{lcm}(a, b) = \prod p_i^{\max(\alpha_i, \beta_i)},\] and since \(\min + \max = \alpha + \beta\), this gives a second proof that \(\gcd \cdot \operatorname{lcm} = ab\). With \(360 = 2^3 3^2 5\) and \(84 = 2^2 3 \cdot 7\): \(\gcd = 2^2 \cdot 3 = 12\) and \(\operatorname{lcm} = 2^3 3^2 5 \cdot 7 = 2520\).

Unique factorization also gives a strong irrationality theorem: if \(n\) is a positive integer that is not a perfect \(k\)-th power, then \(\sqrt[k]{n}\) is irrational. Proof: if \(\sqrt[k]{n} = a/b\), then \(nb^k = a^k\). In the factorization of \(a^k\) and \(b^k\), every exponent is a multiple of \(k\), so the same is true of \(n\), which makes \(n\) a perfect \(k\)-th power. So \(\sqrt 2\), \(\sqrt 12\) and \(\sqrt[3]{9}\) are irrational, all at once.

And it counts divisors: \(n = \prod p_i^{e_i}\) has exactly \((e_1 + 1)(e_2 + 1)\cdots(e_r + 1)\) positive divisors, since each exponent \(f_i\) can be chosen independently from \(0, \ldots, e_i\). So 360 has \(4 \cdot 3 \cdot 2 = 24\) divisors. Lesson 7 develops this into the theory of arithmetic functions.

Unique factorization is not automatic

Hilbert gave a simple example showing why the theorem needs proof. Consider only the numbers \(1, 5, 9, 13, 17, 21, \ldots\) of the form \(4k + 1\). Products of such numbers stay in the set. Call a member of the set irreducible if it is not a product of two smaller members other than 1. Then 9, 21 and 49 are irreducible here, since their only factorizations in the integers use 3 and 7, which are not in the set. But \[441 = 9 \cdot 49 = 21 \cdot 21,\] two different factorizations into irreducibles. What fails is Euclid's lemma: 21 divides \(9 \cdot 49\) but divides neither factor within the set. The same failure occurs in the ring \(\mathbb{Z}[\sqrt{-5}]\), where \(6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})\), and in the nineteenth century this phenomenon derailed several attempted proofs of Fermat's last theorem and led Kummer and Dedekind to invent ideals, the subject of MATH-323.

Primes by computer

The program sieves the primes up to a million, compares \(\pi(x)\) with \(x/\ln x\), factors numbers by trial division, checks the Euclid numbers \(p_1\cdots p_k + 1\), and verifies Hilbert's example.

import math

def sieve(N):
    is_p = bytearray([1]) * (N + 1)
    is_p[0:2] = b"\x00\x00"
    for p in range(2, math.isqrt(N) + 1):
        if is_p[p]:
            is_p[p*p::p] = bytearray(len(range(p*p, N + 1, p)))
    return [i for i in range(N + 1) if is_p[i]]

P = sieve(10**6)
print("primes below 50:", [p for p in P if p < 50])
for x in [10**2, 10**3, 10**4, 10**5, 10**6]:
    pi = sum(1 for p in P if p <= x)
    print(f"pi({x}) = {pi}, x/ln x = {x / math.log(x):.1f}, ratio = {pi / (x / math.log(x)):.3f}")

def factor(n):
    f, d = {}, 2
    while d * d <= n:
        while n % d == 0:
            f[d] = f.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        f[n] = f.get(n, 0) + 1
    return f

for n in [360, 2026, 30031, 2**32 + 1, 1234567890]:
    print(n, "=", " * ".join(f"{p}^{e}" if e > 1 else str(p) for p, e in factor(n).items()))

prod = 1
for p in P[:10]:
    prod *= p
    print(f"product of primes up to {p} plus 1:", prod + 1, factor(prod + 1))

H = [n for n in range(1, 500) if n % 4 == 1]
irred = [n for n in H if n > 1 and not any(n % d == 0 and (n // d) in H for d in H if 1 < d < n)]
print("Hilbert irreducibles below 100:", [n for n in irred if n < 100])
print("441 = 9*49 = 21*21:", 9 * 49 == 21 * 21 == 441, all(m in irred for m in (9, 21, 49)))

primes below 50: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
pi(100) = 25, x/ln x = 21.7, ratio = 1.151
pi(1000) = 168, x/ln x = 144.8, ratio = 1.161
pi(10000) = 1229, x/ln x = 1085.7, ratio = 1.132
pi(100000) = 9592, x/ln x = 8685.9, ratio = 1.104
pi(1000000) = 78498, x/ln x = 72382.4, ratio = 1.084
360 = 2^3 * 3^2 * 5
2026 = 2 * 1013
30031 = 59 * 509
4294967297 = 641 * 6700417
1234567890 = 2 * 3^2 * 5 * 3607 * 3803
product of primes up to 2 plus 1: 3 {3: 1}
product of primes up to 3 plus 1: 7 {7: 1}
product of primes up to 5 plus 1: 31 {31: 1}
product of primes up to 7 plus 1: 211 {211: 1}
product of primes up to 11 plus 1: 2311 {2311: 1}
product of primes up to 13 plus 1: 30031 {59: 1, 509: 1}
product of primes up to 17 plus 1: 510511 {19: 1, 97: 1, 277: 1}
product of primes up to 19 plus 1: 9699691 {347: 1, 27953: 1}
product of primes up to 23 plus 1: 223092871 {317: 1, 703763: 1}
product of primes up to 29 plus 1: 6469693231 {331: 1, 571: 1, 34231: 1}
Hilbert irreducibles below 100: [5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97]
441 = 9*49 = 21*21: True True

The output shows the ratio \(\pi(x)/(x/\ln x)\) rising slightly and then, from \(x = 1000\) on, drifting slowly down toward 1, Fermat's number \(2^{32} + 1\) splitting as \(641 \cdot 6700417\) (Euler's discovery in 1732, which disproved Fermat's guess that all numbers \(2^{2^n} + 1\) are prime), and several Euclid numbers that are composite. Trial division is fine for numbers of 15 digits or so; lesson 11 describes far faster methods.