Prime numbers

What a prime is and why 1 is not one, why there are infinitely many, why every number has exactly one factorisation into primes, and why the sieve of Eratosthenes only starts striking out at the square of a prime.

The primes are the building blocks from which all other numbers are composed by multiplication. Around 300 BC Euclid proved in the Elements that there are infinitely many, and with the lemma that bears his name he laid the ground for the second basic fact: that every number splits into primes in exactly one way. The first complete statement with proof is usually credited to Gauss in 1801. This chapter presents both proofs.

Definition

A number $p \in \mathbb{N}$ is called prime if $p \ge 2$ and $p$ has no divisors apart from $1$ and $p$ :

\begin{aligned} p \text{ prime} \;:\Longleftrightarrow\;& p \ge 2 \text{ and for all } d \in \mathbb{N} \\ & d \mid p \Rightarrow d = 1 \lor d = p. \end{aligned}

A number $n \ge 2$ that is not prime is called composite.

Why is 1 excluded, even though it too is divisible only by 1 and itself? Because otherwise factorisation into primes would no longer be unique: $6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3$ . This is not a discovery but a convention that has proven its worth. Into the early twentieth century some mathematicians still counted 1, and the page The order of the primes argues for a different division in which 1 plays a special role alongside 2 and 3. Both are a matter of definition, not of truth.

Every number has a prime divisor

Theorem 1

Every number $n \ge 2$ has a divisor that is prime. More precisely: the smallest divisor $d > 1$ of $n$ is prime.

Proof

The set of divisors $d > 1$ of $n$ is not empty, since it contains $n$ . Let $d$ be its smallest element. If $d$ had a divisor $e$ with $1 < e < d$ , then by Chapter 3, Theorem 1 $e$ would also divide $n$ and be smaller than $d$ . That contradicts the choice of $d$ . So $d$ is prime.

∎

There are infinitely many

Theorem 2

There are infinitely many primes.

Proof

Let $p_1, p_2, \dots, p_k$ be any primes. We show that there is another one. Let

N := p_1 \cdot p_2 \cdots p_k + 1.

By Theorem 1, $N$ has a prime divisor $q$ . If $q$ were one of the $p_i$ , it would divide the product $p_1 \cdots p_k$ and the number $N$ , and so by Chapter 3, Theorem 1 also their difference 1. That is impossible. So $q$ is a new prime. No finite list contains them all.

∎

This is how the proof stands in Euclid (Elements IX 20). It does not say, by the way, that $N$ itself is prime: $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$ . It only says that $N$ has a prime divisor not yet on the list. The Lean version below uses the factorial $n! + 1$ instead of the product, and so shows that for every number $n$ there is a larger prime.

Euclid’s lemma

Theorem 3

If a prime $p$ divides a product $ab$ , it divides one of the factors:

p \mid ab \;\Longrightarrow\; p \mid a \;\lor\; p \mid b.

Proof

Suppose $p \nmid a$ . The divisor $\gcd(p, a)$ of $p$ is 1 or $p$ , and $p$ is ruled out because $p$ does not divide $a$ . So $\gcd(p, a) = 1$ , and by Chapter 3, Theorem 4 there are integers $x, y$ with $1 = px + ay$ . Multiplied by $b$ :

b = p\,(bx) + (ab)\,y.

Both terms are divisible by $p$ , so $b$ is too.

∎

For composite numbers this fails: $6 \mid 4 \cdot 9$ , but $6 \nmid 4$ and $6 \nmid 9$ . The lemma is exactly the property that makes primes building blocks, and it is needed in Chapter 6 to show how many parts a figure $\{n/k\}$ has.

Unique factorisation

Theorem 4

Every number $n \ge 2$ is a product of primes, and this representation is unique apart from the order.

Proof

Existence, by induction: suppose all numbers from 2 to $n - 1$ are products of primes. If $n$ is prime, we are done. Otherwise $n = ab$ with $2 \le a, b < n$ , and $a$ and $b$ are products of primes by assumption, hence so is $n$ .

Uniqueness: let $p_1 \cdots p_r = q_1 \cdots q_s$ with primes $p_i, q_j$ . Then $p_1$ divides the right-hand product, and by Theorem 3, applied several times, one of the $q_j$ . Since $q_j$ is prime, $p_1 = q_j$ . Cancel $p_1$ on both sides and repeat the argument with the remaining factors until none are left.

∎

Theorem 4 is called the fundamental theorem of arithmetic. It is the reason the primes are called the atoms of the numbers. Without it nothing could be read off reliably from the factorisation of a number.

The sieve of Eratosthenes

How do you find all primes up to a bound? Eratosthenes of Cyrene, head of the library of Alexandria around 240 BC, wrote the numbers down and struck out the multiples of each prime found, one after another. What remains is prime. A theorem shows why much work can be saved.

Theorem 5

If $n \ge 2$ is composite, then $n$ has a prime divisor $p \le \sqrt{n}$ , that is with $p^2 \le n$ .

Proof

Let $n = ab$ with $2 \le a \le b$ . Then $a^2 \le ab = n$ . A prime divisor $p$ of $a$ by Theorem 1 also divides $n$ , and $p^2 \le a^2 \le n$ .

∎

For the sieve this means two things. First, the multiples of a prime $p$ need only be struck out from $p^2$ on, since every smaller multiple has a smaller prime divisor and is already struck out. Second, you can stop as soon as $p^2$ exceeds the bound. For the numbers up to 100, 2, 3, 5 and 7 are therefore enough.

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100

The sieve up to 100. Each press takes the next prime and strikes out its multiples from its square on: 4, 9, 25, 49. After that the work is done, since 11² is already larger than 100.

Here lies the mathematical core of an observation that carries many pages of this website: after the multiples of 2 and 3 have been struck out, the first number the sieve still hits is $25 = 5^2$ . That is why from 2 to 24 all numbers divisible neither by 2 nor by 3 are prime (see The “disorder” of the primes). This is Theorem 5 for the prime 5, and the next chapter makes clear why these numbers are exactly the twin places $6n \pm 1$ .

Checked by computer: the proof in Lean

IsPrime is the definition above. prime_divisor is Theorem 1, proven by strong induction (Nat.strongRecOn): if $n$ is not prime it has a smaller divisor, for which the statement already holds. fact is the factorial, dvd_fact shows that every number from 1 to $n$ divides $n!$ , and infinitely_many is Theorem 2 with $n! + 1$ instead of the product. euclid_lemma is Theorem 3. Lean takes the step via the gcd from its library, where Chapter 3, Theorem 4 is already proven.

/-! Chapter 4: prime numbers -/

def IsPrime (n : Nat) : Prop :=
  2 ≤ n ∧ ∀ d, d ∣ n → d = 1 ∨ d = n

/-- Theorem 1: Every number n ≥ 2 has a prime divisor. -/
theorem prime_divisor (n : Nat) (h : 2 ≤ n) :
    ∃ p, IsPrime p ∧ p ∣ n := by
  induction n using Nat.strongRecOn with
  | ind n ih =>
    by_cases hp : IsPrime n
    · exact ⟨n, hp, Nat.dvd_refl n⟩
    · -- n is not prime: there is a divisor d with 1 < d < n
      have : ∃ d, d ∣ n ∧ d ≠ 1 ∧ d ≠ n := by
        apply Classical.byContradiction
        intro hne
        apply hp
        refine ⟨h, fun d hd => ?_⟩
        apply Classical.byContradiction
        intro hd2
        apply hne
        exact ⟨d, hd, fun h1 => hd2 (Or.inl h1),
          fun h2 => hd2 (Or.inr h2)⟩
      obtain ⟨d, hd, hd1, hdn⟩ := this
      have hd0 : 0 < d := Nat.pos_of_dvd_of_pos hd (by omega)
      have hdle : d ≤ n := Nat.le_of_dvd (by omega) hd
      obtain ⟨p, hp, hpd⟩ := ih d (by omega) (by omega)
      exact ⟨p, hp, Nat.dvd_trans hpd hd⟩

/-- The factorial n! = 1 · 2 · … · n -/
def fact : Nat → Nat
  | 0 => 1
  | n + 1 => (n + 1) * fact n

theorem fact_pos (n : Nat) : 0 < fact n := by
  induction n with
  | zero => decide
  | succ n ih =>
    simp only [fact]
    exact Nat.mul_pos (by omega) ih

/-- Every number d from 1 to n divides n! -/
theorem dvd_fact (d n : Nat) (h1 : 1 ≤ d) (h2 : d ≤ n) :
    d ∣ fact n := by
  induction n with
  | zero => omega
  | succ n ih =>
    by_cases hd : d = n + 1
    · subst hd
      exact Nat.dvd_mul_right _ _
    · exact Nat.dvd_trans (ih (by omega)) (Nat.dvd_mul_left _ _)

/-- Theorem 2 (Euclid): For every number n there is a
    larger prime. -/
theorem infinitely_many (n : Nat) : ∃ p, IsPrime p ∧ n < p := by
  have hf := fact_pos n
  obtain ⟨p, hp, hpd⟩ := prime_divisor (fact n + 1) (by omega)
  refine ⟨p, hp, ?_⟩
  apply Classical.byContradiction
  intro hle
  have hp2 := hp.1
  have hp1 : 1 ≤ p := by omega
  have h1 : p ∣ fact n := dvd_fact p n hp1 (by omega)
  have h2 : p ∣ 1 := (Nat.dvd_add_right h1).mp hpd
  have := Nat.le_of_dvd (by decide) h2
  have := hp.1
  omega

/-- Theorem 3 (Euclid's lemma): If a prime divides a product,
    it divides one of the factors. The step "from gcd(p, a) = 1
    and p ∣ a · b follows p ∣ b" is in Lean's library and
    proven there. -/
theorem euclid_lemma (p a b : Nat) (hp : IsPrime p) (h : p ∣ a * b) :
    p ∣ a ∨ p ∣ b := by
  by_cases ha : p ∣ a
  · exact Or.inl ha
  · right
    -- gcd(p, a) divides p, so it is 1 or p. It is not p,
    -- because p does not divide a.
    have hg : Nat.gcd p a = 1 := by
      rcases hp.2 (Nat.gcd p a) (Nat.gcd_dvd_left p a) with h1 | h2
      · exact h1
      · exfalso
        apply ha
        have := Nat.gcd_dvd_right p a
        rw [h2] at this
        exact this
    exact Nat.Coprime.dvd_of_dvd_mul_left hg h

Try it in the browser at live.lean-lang.org ↗How to read Lean

Sources and further reading

Sources

Euclid, Elements, around 300 BC, book VII, 30 to 32, and book IX, 20
Nicomachus of Gerasa, Introduction to Arithmetic, around 100 AD, book I, ch. 13 (the sieve of Eratosthenes)
Carl Friedrich Gauß, Disquisitiones arithmeticae, Leipzig 1801, article 16

Prime numbers

Definition

Every number has a prime divisor

There are infinitely many

Euclid’s lemma

Unique factorisation

The sieve of Eratosthenes

Sources

Further reading