Are there infinitely many primes?
We'll give a proof, due to Euclid, to show that there must be infinitely many primes. We will show that if there were only finitely many primes, it would lead to a contradiction.
First note that if two numbers differ by one, then they cannot have any common factors (or else that common factor would also divide 1).
So now suppose there are only finitely many primes
p_{1}, p_{2}, ..., p_{n}. Then
by multiplying them all together, we get a (very large!)
integer N that must be divisible by all the primes.
But then (N+1) cannot be divisible by any prime, because N and N+1 have no common factors.
This is clearly impossible because it contradicts the fact that every integer greater than 1 can be factored into primes.
Presentation Suggestions:
Give a simple example: suppose 2, 3, and 5 were the only
primes. Then (2)(3)(5)+1=31 cannot be divisible by any of
them and must be divisible by some other prime number (in this
case 31) which shows that 2, 3, 5 could not be the complete
set of primes.
Note that this proof does not say that N+1 necessarily itself must be a prime... it just shows that it must be divisible by one that was not in the original list.
The Math Behind the Fact:
Proving a statement by showing that its negation leads to
a contradiction is called a proof by contradiction.
For more
refined questions about how many primes there are, see
Sum of Prime Reciprocals.
How to Cite this Page:
Su, Francis E., et al. "How many Primes?."
Math Fun Facts.
<http://www.math.hmc.edu/funfacts>.
