Indirect Proof (Proof by Contradiction)

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,\mathrm{...},p_n$ , where $p_n$ is the largest prime.

Consider the number $q=p_1\cdot p_2\cdot \mathrm{...}\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<n$ ; 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.