- An assumption or
- A conclusion, clearly following from an assumption or previously proved result.

A well written proof will flow. That is, the reader should feel as though they are being taken on a ride that takes them directly and inevitably to the desired conclusion without any distractions about irrelevant details. Each step should be clear or at least clearly justified. A good proof is easy to follow.

When you are finished with a proof, apply the above simple test to every sentence: is it clearly (a) an assumption or (b) a justified conclusion? If the sentence fails the test, maybe it doesn't belong in the proof.

Before we begin the proof, let's recall a few definitions. A real number
is called **rational **if it can be expressed as the ratio of two integers:
p/q. The ancient Greeks thought that all numbers were rational. A number
that is not rational would be called **irrational**. You probably believe
that p is irrational. (It might surprise you that this is not easy to
prove.) When the Greeks proved that the square root of 2 is not a rational
number, the very foundations of arithmetic were called into question. This
is one of the reasons that Greek geometry subsequently flourished--all
numbers could be treated geometrically without reference to rationality.

Another fact that we will need is the **Fundamental Theorem of Arithmetic**.
This exciting sounding theorem is nothing more than the fact that every
positive integer has a unique representation as a product of prime numbers.
The technique of proof we will use is proof by **contradiction **. You
do not need any specialized knowledge to understand what this means. It
is very simple. We will assume that the square root of 2 **is** a rational
number and then arrive at a contradiction. Make sure you understand every
line of the proof.

**Theorem.** The square root of 2 is an irrational number.

**Proof.** Let's represent the square root of 2 by s. Then, by definition,
s satisfies the equation

If s were a rational number, then we could write

where p and q are a pair of integers. Infact, by dividing out the common multiple if neccessary, we may even assume p and q have no common multiple (other than 1). If we now substitute this into the first equation we obtain, after a little algebra, the equation

But now, by the Fundamental Theorem of Arithmetic, 2 must appear in
the prime factorization of the number p^{2} (since it appears in
the same number 2 q^{2}). Since 2 itself is a prime number, 2 must
then appear in the prime factorization of the number p. But then, 2^{2}
would appear in the prime factoriztion of p^{2}, and hence in 2
q^{2}. By dividing out a 2, it then appears that 2 is in the prime
factorization of q^{2}. Like before (with p^{2}) we can
now conclude 2 is a prime factor of q. But now we have p and q sharing
a prime factor, namely 2. This violates our assumption above (see if you
can find it) that p and q have no common multiple other than 1.

q

** Next==>**Direct Proofs