Chapter 2: Proof by Contradiction

Proof (by contradiction)

Step 1: Set up the assumption for the proof by contradiction.

Assume that $\sqrt{2}$ is rational.

Step 2: Express the assumption as a formula.

By the definition of a rational number, there exist coprime integers $p, q$ (with $q \neq 0$) such that

$$\sqrt{2} = \dfrac{p}{q}$$

(that is, $\sqrt{2}$ can be written as a fraction in lowest terms).

Step 3: Square both sides.

$$2 = \dfrac{p^2}{q^2}$$

Multiplying both sides by $q^2$ and rearranging gives

$$p^2 = 2q^2 \quad \cdots (*)$$

Step 4: Show that $p$ is even.

From $(*)$ we have $p^2 = 2q^2$, so $p^2$ is even.

Here we use the lemma: "If $n^2$ is even, then $n$ is even" (proved below).

Hence $p$ is even, and there exists an integer $k$ such that

$$p = 2k.$$

Step 5: Show that $q$ is also even.

Substituting $p = 2k$ into $(*)$:

\begin{align} (2k)^2 &= 2q^2 \\ 4k^2 &= 2q^2 \\ 2k^2 &= q^2 \end{align}

Thus $q^2$ is even, so $q$ is also even.

Step 6: Point out the contradiction.

We have shown that both $p$ and $q$ are even.

But this contradicts the assumption in Step 2 that "$p$ and $q$ are coprime".

(If both $p$ and $q$ are even, they share the common divisor $2$.)

Step 7: State the conclusion.

Since a contradiction has been derived, the initial assumption "$\sqrt{2}$ is rational" is false.

Therefore $\sqrt{2}$ is irrational. $\square$

Proof of the lemma (by contrapositive)

We prove the contrapositive: "If $n$ is odd, then $n^2$ is odd".

If $n$ is odd, then there exists an integer $m$ such that $n = 2m + 1$.

\begin{align} n^2 &= (2m + 1)^2 \\ &= 4m^2 + 4m + 1 \\ &= 2(2m^2 + 2m) + 1. \end{align}

Since $2m^2 + 2m$ is an integer, $n^2$ is odd.

The contrapositive is true, so the original statement is also true. $\square$

Proof (by contradiction)

Step 1: Set up the assumption.

Assume that there are only finitely many primes.

List all primes as $p_1, p_2, \ldots, p_n$.

Step 2: Construct a new number.

Consider the number $N$ defined by

$$N = p_1 \cdot p_2 \cdot p_3 \cdots p_n + 1$$

(the product of all the primes plus $1$).

Step 3: Examine the properties of $N$.

Since $N > 1$, $N$ is either prime itself or has a prime factor.

Step 4: Derive a contradiction.

For any prime $p_i$ (with $i = 1, 2, \ldots, n$), dividing

$$N = p_1 p_2 \cdots p_n + 1$$

by $p_i$: since $p_1 p_2 \cdots p_n$ is divisible by $p_i$, we have

$$N \equiv 1 \pmod{p_i}.$$

That is, dividing $N$ by $p_i$ leaves remainder $1$.

Hence $N$ is not divisible by any $p_i$.

Step 5: Point out the contradiction.

Although $N > 1$, $N$ is not divisible by any prime.

This contradicts the fact that "every integer greater than $1$ has a prime factor".

(Either $N$ itself is a new prime, or it has a prime factor not in the list.)

Step 6: Conclusion.

Since a contradiction has been derived, the assumption that "there are finitely many primes" is false.

Therefore there are infinitely many primes. $\square$