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 p1, p2, …, pn. 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. <https://www.math.hmc.edu/funfacts>.
References:
P. Ribenboim, The New Book of Prime Number Records, 1996.
Fun Fact suggested by:
Francis Su