Proof by Contradiction | Real Analysis

Assume there are only finitely many primes and derive a contradiction. Watch a new prime slip outside the list.

Proof by contradiction assumes the opposite side. Push the false side until it clashes with itself. Then the original claim must be true. Multiplying all the primes and adding one builds that clash.

For example, suppose a biggest number exists. Add one and a bigger number appears. The assumption destroys itself. Euclid's prime proof uses exactly this move.

Examples & Exercises

Prove Euclid's theorem completely: there are infinitely many primes.

Use proof by contradiction — assume $p_1, \ldots, p_k$ are all the primes, and show that $N = p_1 \cdots p_k + 1$ (i) has a prime factor, since $N \ge 2$ , and (ii) that this factor cannot equal any $p_i$ , deriving a contradiction.

In particular, address the subtlety that $N$ itself need not be prime (for $k = 6$ , $N = 30031 = 59 \times 509$ ).

N = p_1 p_2 \cdots p_k + 1, \qquad N \equiv 1 \pmod{p_i} \ \text{for all } i

k = 6:\quad N = 30031 = 59 \times 509

k = 6

P = 30030

N = 30031 = 59 \times 509

—

N

is composite, but its prime factors

59

and

509

are new primes off the list

\{2, 3, 5, 7, 11, 13\}

Show proof

We argue by contradiction.
Suppose there are only finitely many primes — a complete list $p_1, \ldots, p_k$ ( $k \ge 1$ ).
Put $P = p_1 \cdots p_k$ and $N = P + 1$ ; then $N \ge 3 \ge 2$ .
Lemma: every integer $\ge 2$ has a prime factor.
Proof (strong induction): for $n = 2$ , $n$ itself is prime.
For $n > 2$ , either $n$ is prime or $n = ab$ with $1 < a, b < n$ ; in the composite case the induction hypothesis gives $a$ a prime factor $q$ , and $q \mid a \mid n$ , so $q$ is a prime factor of $n$ .
Applying this to $N$ yields a prime factor $q$ of $N$ .
$q$ differs from every $p_i$ .
Indeed, $p_i \mid P$ for each $i$ , so $N = P + 1 \equiv 1 \pmod{p_i}$ : no $p_i$ divides $N$ .
But $q \mid N$ , hence $q \ne p_i$ for every $i$ .
So $q$ is a prime missing from the supposedly complete list — a contradiction.
Hence there are infinitely many primes. ∎
The subtlety: $N$ itself need not be prime.
For $k = 6$ , $P = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 = 30030$ and $N = 30031 = 59 \times 509$ is composite.
The proof is unaffected — its claim is "\emph{every} prime factor of $N$ is new", not " $N$ is a new prime".
The proof does pin down that a new prime is among the factors of $N$ , but identifying it requires factoring $N$ .

Prove by contradiction that $\log_2 5$ is irrational.

Hint: if $\log_2 5 = \frac{p}{q}$ with $p, q$ positive integers, then $2^p = 5^q$ — the left side is even and the right side is odd.

\log_2 5 = \frac{p}{q} \;\Rightarrow\; 5 = 2^{p/q} \;\Rightarrow\; 5^q = 2^p

2^p \text{ is even } (p \ge 1), \qquad 5^q \text{ is odd}

The scene preset is the default

k = 4

(

P = 210

N = 211

) — this problem is about the shape of proof by contradiction itself, not the scene's numbers.

Show proof

We argue by contradiction.
Suppose $\log_2 5$ is rational.
Since $\log_2 5 > \log_2 4 = 2 > 0$ , we can write $\log_2 5 = \frac{p}{q}$ with $p, q$ positive integers — in particular $p \ge 1$ .
By the definition of the logarithm, $5 = 2^{p/q}$ , and raising both sides to the power $q$ gives $5^q = 2^p$ .
But $p \ge 1$ makes $2^p = 2 \cdot 2^{p-1}$ even, while $5^q$ , a product of odd numbers, is odd.
An even number cannot equal an odd number — a contradiction.
Hence $\log_2 5$ is irrational. ∎
Note: there is no need to put $\frac{p}{q}$ in lowest terms — the parity argument alone suffices. The deeper reason is the fundamental theorem of arithmetic (unique prime factorization): $2^p$ has only the prime factor 2 and $5^q$ only the prime factor 5, so the two powers with positive exponents can never agree.

Prove by contradiction: if $r$ is rational and $x$ is irrational, then $r + x$ is irrational.

r + x = s \in \mathbb{Q} \;\Rightarrow\; x = s - r \in \mathbb{Q}

The scene preset is the default

k = 4

(

P = 210

N = 211

) — this problem is about the shape of proof by contradiction itself, not the scene's numbers.

Show proof

We argue by contradiction.
Suppose $r + x$ is rational, and put $s = r + x \in \mathbb{Q}$ .
Then $x = s - r$ .
A difference of rationals is rational: if $r = \frac{a}{b}$ and $s = \frac{c}{d}$ (with $a, c \in \mathbb{Z}$ , $b, d \in \mathbb{Z}$ , $b, d \ne 0$ ), then $x = s - r = \frac{cb - ad}{bd}$ , and $cb - ad \in \mathbb{Z}$ with $bd \ne 0$ , so $x \in \mathbb{Q}$ .
This contradicts the assumption that $x$ is irrational.
Hence $r + x$ cannot be rational — it is irrational.
∎ (The same argument shows $rx$ is irrational for rational $r \ne 0$ and irrational $x$ : if $rx = s$ then $x = s/r$ is a quotient of rationals.)