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
For n =2, the base step
For the induction step , we must assume the precedent and deduce the antecedent.
If then by , x is either prime or a composite.
If and is prime then is prime.
If and is not prime then there are natural numbers such that and .
Since , then by , are either primes or composites.
The theorem follows by induction.
- Which proofs do you consider beautiful?
- What did you think was proved but learned isn’t?
- Which proofs are you currently trying to grasp?