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 , where is the largest prime.
Consider the number formed by multiplying all these primes and then adding .
We claim that is a prime. It cannot be divided evenly by any prime with ; this will always result in a remainder of . And if it could be divided the that evently by a composite number , then it could also be divided by some prime factor of ... but this again results in a remainder of . So the only factors of are and itself.
This means that is a prime number larger than . But we assumed was the largest prime, so this is a contradiction.
Therefore, there are infinitely many primes.