Proof by contradiction/Square root of 2 and Euclid/Introduction/Section

We give two classical examples for a proof by contradiction.

Theorem

There does not exist a rational number such that its square equals ${}2$. This means that the real number ${}{\sqrt {2}}$ is irrational.

Proof

We make the assumption that there exists some rational number whose square equals ${}2$, and we have to derive a contradiction from this. Our assumption means the existence of

${}x\in \mathbb {Q} \,$

fulfilling the property

${}x^{2}=2\,.$

A rational number can be written as a fraction, where numerator and denominator are integers. Hence, the rational number ${}x$ has the form

${}x={\frac {a}{b}}\,.$

Moreover, we can suppose that this fraction has been reduced to its lowest terms, so that the greatest common divisor of ${}a$ and ${}b$ is ${}1$. In fact it is enough to suppose that at least one of ${}a$ and ${}b$ are odd (if both are even we can divide both by ${}2$ until one gets odd). The property

${}x^{2}=2\,$

means then

${}x^{2}={\left({\frac {a}{b}}\right)}^{2}={\frac {a^{2}}{b^{2}}}=2\,.$

Multiplication by ${}b^{2}$ yields

${}2b^{2}=a^{2}\,$

(this is an equation in ${}\mathbb {Z}$ and even in ${}\mathbb {N}$). This equation means that ${}a^{2}$ is even, since ${}a^{2}$ is a multiple of ${}2$. This implies that ${}a$ itself is even, because the square of an odd number is again odd. Therefore, we can write

${}a=2c\,$

with an integer ${}c$. Putting this into the equation, we deduce

${}2b^{2}=(2c)^{2}=2^{2}c^{2}\,.$

Dividing both sides by ${}2$ we obtain

${}b^{2}=2c^{2}\,.$

Hence, also ${}b^{2}$ is even and so ${}b$ is even. But this is a contradiction, as ${}a$ and ${}b$ are not both even.

$\Box$

The following theorem is called Theorem of Euclid.

Theorem

There exist infinitely many prime numbers.

Proof

We assume that the set of all prime numbers is finite, say ${}\{p_{1},p_{2},\ldots ,p_{r}\}$ is a complete list of all prime numbers. We consider the number

${}N=p_{1}\cdot p_{2}\cdot p_{3}\cdots p_{r}+1\,.$

This number can not be divided by any of the prime numbers ${}p_{i}$, since the reminder of ${}N$ by division through ${}p_{i}$ is always ${}1$. Hence, the prime factors of ${}N$, which exist due to fact, are not contained in the given set. This is a contradiction.

$\Box$