Argument by Contradiction. There are in?nitely many prime numbers.

Argument by Contradiction

The method of argument by contradiction proves a statement in the following way: First, the statement is assumed to be false. Then, a sequence of logical deductions yields a conclusion that contradicts either the hypothesis (indirect method ), or a fact known to be true (reductio ad absurdum).

This contradiction implies that the original statement must be true. This is a method that Euclid loved, and you can ?nd it applied in some of the most beautiful proofs from his Elements. Euclid’s most famous proof is that of the in?nitude of prime numbers.

Euclid’s theorem.

There are in?nitely many prime numbers.

Proof. Assume, to the contrary, that only ?nitely many prime numbers exist. List them as p1 = 2, p2 = 3, p3 = 5, . . . , pn. The number N = p1p2 · · · pn + 1 is divisible by a prime p, yet is coprime to p1, p2, . . . , pn. Therefore, p does not belong to our list of all prime numbers, a contradiction. Hence the initial assumption was false, proving that there are in?nitely many primes.