The Fundamental Theory Of Arithmetic

Through many births I have wandered on and on,

Searching for, but never finding, the builder of this house.

Siddhārtha Gautama

While doing the coursera course Introduction to Mathematical Thinking I was exposed to the following proof, which is the first I’ve understood fully. The argument is elegant and, as it turns out, over 2000 years old! Euclid’s Elements first outlines this proof.

Theorem: Every natural number greater than 1 is either prime or a product of primes (composite).

Proof: Using a proof of induction, starting from n = 2

Let \( A(n) = \forall x [2 \leq x \leq n \implies \text{x is prime or a composite}]\)

The base step, for n = 2:

\(A(2)\) =”2 is either prime or a composite”. Which is true.

For the induction step, we must assume the precedent and deduce the antecedent.

Let \(A(n+1) = \forall x [2 \le x \le (n+1) \implies \text{x is prime or a composite}]\)

If \(x \le n\) then by \(A(n)\), \(x\) is either prime or a composite.

If \(x = (n+1)\) and \((n+1)\) is prime then \(x\) is prime.

If \(x = (n+1)\) and \((n+1)\) is not prime then there are natural numbers \(p,q\) such that \(1 \lt p,q \lt (n+1)\) and \((n+1) = pq\).

Since \(2 \leq p \leq q \leq n\), then by \(A(n)\), \(p,q\) are either primes or composites.

The theorem follows by induction

$\square$

Discussion Points

• Which proofs do you consider beautiful?
• What did you think was proved but learned isn’t?
• Which proofs are you currently trying to grasp?