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 Induction

Let $\mathrm{A}\left(\mathrm{n}\right)=\forall \mathrm{x}[2\le \mathrm{x}\le \mathrm{n}\Rightarrow \text{xisprimeoracomposite}]$

For n =2, the base step $A\left(2\right)=\text{\u201c2iseitherprimeoracomposite\u201d}$

For the induction step $A\left(n\right)\Rightarrow A(n+1)$, we must assume the precedent and deduce the antecedent.

Let $A(n+1)=\forall x[2\le x\le (n+1)\Rightarrow \text{xisprimeoracomposite}]$

If $x\le n$ then by $A\left(n\right)$, 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<p,q<(n+1)$ and $(n+1)=pq$.

Since $2\le p\le q\le n$, then by $A\left(n\right)$, $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?