hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su

The Math Fun Facts App!

List All : List Recent : List Popular
About Math Fun Facts / How to Use
Contributors / Fun Facts Home
© 1999-2010 by Francis Edward Su

From the Fun Fact files, here is a Fun Fact at the Medium level:

# How many Primes?

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.

Su, Francis E., et al. "How many Primes?." Math Fun Facts. <http://www.math.hmc.edu/funfacts>.

References:
P. Ribenboim, The New Book of Prime Number Records, 1996.

Keywords:    proof by contradiction, number theory
Subjects:    number theory
Level:    Medium
Fun Fact suggested by:   Francis Su
Suggestions? Use this form.
4.19
current
rating
Click to rate this Fun Fact...
*   Awesome! I totally dig it!
*   Fun enough to tell a friend!
*   Mildly interesting
*   Not really noteworthy
and see the most popular Facts!
New: get the MathFeed iPhone App!

Brings you news and views on math:
showcasing its power, beauty, and humanity

Want another Math Fun Fact?

For more fun, tour the Mathematics Department at Harvey Mudd College!