Prove that there exists an infinitely large number of primes.
Proof by contradiction:
Suppose there is a largest prime number P. Let c = the product of all primes less than or equal to P.
Now consider c + 1. c + 1 modulo any prime number is 1, so c + 1 is not divisible by any prime number less than or equal to P. Therefore c + 1 is itself prime. We know that c + 1 is larger than c, and we know that c is larger than P, since it is the product of P and some large positive integer. Thus, c + 1 is larger than P.
However, it is a given that there are no prime numbers larger than P. Therefore, a contradiction exists, and there is no largest prime number. Thus, there is an infinite number of primes.
Solution
