# Indirect Proof (Proof by Contradiction)

To prove a theorem indirectly, you assume the hypothesis is false, and then arrive at a contradiction. It follows the that the hypothesis must be true.

Example:

Prove that there are an infinitely many prime numbers.

Proof. Suppose that the statement is false; that is, suppose there are finitely many primes.

Then we can number the primes p1, p2, ..., pn, where pn is the largest prime.

Consider the number formed by multiplying all these primes and then adding 1.

We claim that q is a prime. It cannot be divided evenly by any prime pi with i < n; this will always result in a remainder of 1. And if it could be divided evently by a composite number c, then it could also be divided by some prime factor of c... but this again results in a remainder of 1. So the only factors of q are 1 and itself.

This means that q is a prime number larger than pn. But we assumed pn was the largest prime, so this is a contradiction.

Therefore, there are infinitely many primes.