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 Induction

Let A(n) =x[ 2xnx is prime or a composite]

For n =2, the base step A(2) = “2 is either prime or a composite”

For the induction step A(n) A(n+1), we must assume the precedent and deduce the antecedent.

Let A(n+1) = x[ 2x(n+1)x is prime or a composite ]

If xn 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<p,q<(n+1) and (n+1) = pq.

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

The theorem follows by induction.

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?

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.