# 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 ${p}_{1},{p}_{2},...,{p}_{n}$ , where ${p}_{n}$ is the largest prime.

Consider the number $q={p}_{1}\cdot {p}_{2}\cdot ...\cdot {p}_{n}+1$ 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 ${p}_{i}$ with $i ; this will always result in a remainder of $1$ . And if it could be divided the that 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 ${p}_{n}$ . But we assumed ${p}_{n}$ was the largest prime, so this is a contradiction.

Therefore, there are infinitely many primes.