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.