# 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 ${\displaystyle {}2}$. This means that the real number ${\displaystyle {}{\sqrt {2}}}$ is irrational.

### Proof

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

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

fulfilling the property

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

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

${\displaystyle {}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 ${\displaystyle {}a}$ and ${\displaystyle {}b}$ is ${\displaystyle {}1}$. In fact it is enough to suppose that at least one of ${\displaystyle {}a}$ and ${\displaystyle {}b}$ are odd (if both are even we can divide both by ${\displaystyle {}2}$ until one gets odd). The property

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

means then

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

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

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

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

${\displaystyle {}a=2c\,}$

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

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

Dividing both sides by ${\displaystyle {}2}$ we obtain

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

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

${\displaystyle \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 ${\displaystyle {}\{p_{1},p_{2},\ldots ,p_{r}\}}$ is a complete list of all prime numbers. We consider the number

${\displaystyle {}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 ${\displaystyle {}p_{i}}$, since the reminder of ${\displaystyle {}N}$ by division through ${\displaystyle {}p_{i}}$ is always ${\displaystyle {}1}$. Hence, the prime factors of ${\displaystyle {}N}$, which exist due to fact, are not contained in the given set. This is a contradiction.

${\displaystyle \Box }$