Math Homework. Do It Faster, Learn It Better.

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.


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 p 2 ... 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.