*Real* Mathematics = Proof

I remember a day in high school when our algebra teacher assigned a simple proof as a homework problem. Another of the students asked plaintively "What does he want?" Proof can be a tough concept to grasp, so I want to illustrate it here. I'll take a landmark in the history of mathematics: The discovery by the Pythagoreans that the square root of 2 is not rational, that is, √(2) is not the quotient of two natural numbers. (The "natural numbers" are just the counting numbers, 1, 2, 3, etc.)

*This has an interesting story associated with it. The Pythagoreans' world-view
centered around the natural numbers; for instance, they discovered that pleasing
harmonies result when the lengths of two plucked strings are a simple ratio,
like 1:2 or 2:3. Anyway, whatever their justification for the importance of
natural numbers, they thought that any fraction was the ratio of two natural
numbers. One of their order, Hippasus, discovered the theorem and proof which
we will explore shortly, which says that the square root of 2 is not the ratio
of any natural numbers. For this heresy, it is said that others of the
Pythagorean order threw Hippasus overboard at sea, drowning him.*

This proof, which is ancient, uses what is called the indirect method. This means that we assume the opposite of what we're trying to prove, and then try to derive a contradiction. This is not as mysterious as it appears to some at first glance. We use a similar idea all the time in our daily lives. For instance, suppose I suspect that my young neighbor Hannah killed President Kennedy. If she did, then she would have had to be in Dallas on that day, so I might try to establish her whereabouts when it happened. And now my theory has a problem: She couldn't have been in Dallas because she was born in 1990, more than two decades after Kennedy was murdered. This contradiction with a known fact establishes that my starting point was incorrect; so Hannah is cleared.

Ok, so that was a pretty trivial example. How about something real? Let's
assume that √(2) = a/b, where a and b are whole numbers, and investigate what
properties a and b must have. If we find that they must have properties that
they can't have, then we know that our assumption was false, namely that √(2)
*cannot* equal a/b for any whole numbers a and b.

Starting with

√(2) = a / b

let's square both sides. We get

2 = a^{2} / b^{2}

and now let's multiply both sides by b^{2} to get

2b^{2} = a^{2}.

Now that's interesting. It says that a^{2} is even, because it's equal
to 2 times another number. What does that say about a itself? Can a be odd?
No, it can't, because the product of two odd numbers is always odd.

(Why is the product of two odd numbers always odd, you ask? Every odd number
is of the form *2n+1*, that is, an even number — *2n* —
plus 1. So let's see what happens when we multiply an odd number by itself:

(2n+1)(2n+1) = 4n^{2} + 4n + 1
= 2(2n^{2} + 2n) + 1

which is 2 times a number, plus 1, which is an odd number.)

So the fact that a^{2} is even tells us that a itself is even, that is,
that a = 2a_{1} for some number a_{1}. I'll just make that
substitution in the equation to get:

2b^{2} = (2a_{1})^{2}
= 4a_{1}^{2}

And now I'll divide both sides by 2 to get, finally,

b^{2} = 2a_{1}^{2}

Now that's interesting too. It says that b^{2} is even, and so we know
that b must be even, by the same logic that we went through for a. In the same
way then we have b = 2b_{1} for some number b_{1}. We'll just
substitute that into the earlier equation to get:

(2b_{1})^{2} = 2a_{1}^{2}

4b_{1}^{2}= 2a_{1}^{2}

and I'll divide through by 2 to get:

2b_{1}^{2}= a_{1}^{2}

Now that's interesting. It means that a_{1}^{2} is even, and
so a_{1} also has to be even. So a_{1} has to be equal to
2a_{2} for some number a_{2}. We substitute that back into
the previous equation and simplify it, thus:

2b_{1}^{2}= (2a_{2})^{2} =
4a_{2}^{2}, so

b_{1}^{2} = 2a_{2}^{2}

Now that's interesting. It means that b_{1}^{2} is even, and
so b_{1} must be even. But by this time, this is getting repetitive.
It's clear that we can go on like this forever, taking a factor of two out of
one side or the other each time. So here's the situation: We assumed that
√(2) = a / b, where a and b are whole numbers, and we discovered that we can take
a factor of 2 out of both a and b, forever. Now how many numbers can you think
of which have an infinite number of factors of 2?

Right; there aren't any. All ordinary whole numbers are finite. They can't have an infinite number of factors. We've proved that our assumption that √(2) = a / b must be false.

## More Power!

Just as there are many routes from one place to another, there are many ways to prove mathematical theorems. Let's see a very short proof that √(2) is irrational, based on factoring numbers.You've probably reduced numbers to their prime factors. Start with any whole number, say 1092, and start looking for smaller numbers that divide it with no remainder. 1092 is even, so we divide by 2 to get 546. That's still even, so we find 1092 = 2*2*273. 273 isn't even so we can stop trying any even divisor. 3 divides 273, so 1092 = 2*2*3*91. Via trial and error, or various clever tricks, we find that 7 divides 91, so 1092 = 2*2*3*7*13. All the divisors are prime, so there the process stops.

You can try different divisors, for instance 182. 1092 = 182*6, and we can push that further since we can see the factors of 6: 1092 = 182*2*3. And 182 is even, so 1092 = 91*2*2*3. Again we have 91 as a factor, and we already know that 91 = 7*13, so 1092 = 2*2*3*7*13. Those are the same factors that we found the first time. Could that be coincidental?

Could be, but it isn't. One of the first big theorems you'll encounter and
prove if you study number theory is the *fundamental theorem of arithmetic*.
This says that the list of factors of any whole number is unique. I'll use that
fundamental property of whole numbers to give a short proof that √(2) is
irrational.

Once again, suppose it isn't. That is, suppose there exist whole numbers *m
* and *n* such that

√(2) = m/n.

Again we square both sides to get

2 = m^{2}/n^{2}.

And again multiply by n^{2} to get

2n^{2} = m^{2}

Now let's use the fundamental theorem of arithmetic on m and n. That says that
m and n have a unique list of prime factors. Say m = a*b*c*d*... and n =
z*y*w*v*.... I don't know how many factors each has; if one of them is prime
then it'd be only one factor, namely itself. But that won't matter. We
substitute the prime factorization of m and n in our last equation and get

2*z*z*y*y*w*w*v*v*... = a*a*b*b*c*c*d*d*...

Now we're almost done. We have a single number written as two lists of prime factors. The fundamental theorem of arithmetic says that the list of prime factors is unique. So those two lists have to be the same. But the one on the left has an odd number of factors (2 and the list of factors from n, each of which appears twice because n is squared), and the list on the right has an even number (the factors of m, each of which appears twice). So they can't be the same. We have our contradiction. √(2) is irrational.