Proof by contradiction/Square root of 2 and Euclid/Introduction/Section
We give two classical examples for a proof by contradiction.
We make the assumption that there exists some rational number whose square equals , and we have to derive a contradiction from this. Our assumption means the existence of
fulfilling the property
A rational number can be written as a fraction, where numerator and denominator are integers. Hence, the rational number has the form
Moreover, we can suppose that this fraction has been reduced to its lowest terms, so that the greatest common divisor of and is . In fact it is enough to suppose that at least one of and are odd (if both are even we can divide both by until one gets odd). The property
means then
Multiplication by yields
(this is an equation in and even in ). This equation means that is even, since is a multiple of . This implies that itself is even, because the square of an odd number is again odd. Therefore, we can write
with an integer . Putting this into the equation, we deduce
Dividing both sides by we obtain
Hence, also is even and so is even. But this is a contradiction, as and are not both even.
The following theorem is called Theorem of Euclid.
We assume that the set of all prime numbers is finite, say is a complete list of all prime numbers. We consider the number
This number can not be divided by any of the prime numbers , since the reminder of by division through is always . Hence, the prime factors of , which exist due to fact, are not contained in the given set. This is a contradiction.