Proof by Contradiction | Real Analysis

Suppose the primes

p_1, \ldots, p_k

were all there are — the chips show the list,

P = p_1 \cdots p_k

, and

N = P+1

N

is divisible by no prime on the list (remainder 1) yet has a prime factor, and that factor is off the list — a contradiction. At

k = 6

N = 30031 = 59 \times 509

is composite and the proof still stands, teaching the shape of contradiction (assume

\lnot P

→ contradiction →

P

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.)