Are there\u00a0infinitely many primes?<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
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).<\/p>\n\n\n\n
So now suppose there are only finitely many primes p1<\/sub>, p2<\/sub>, …, pn<\/sub>. Then by multiplying them all together, we get a (very large!) integer N that must be divisible by all<\/em> 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.<\/p>\n\n\n\n Presentation Suggestions:<\/strong> 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.<\/p>\n\n\n\n The\u00a0Math\u00a0Behind\u00a0the\u00a0Fact:<\/strong> For more refined questions about how many primes there are, see\u00a0Sum of Prime Reciprocals.<\/p>\n\n\n\n How to Cite this Page:<\/strong> References:<\/strong> Fun Fact suggested by: <\/strong> Are there\u00a0infinitely many primes? We’ll give a proof, due to Euclid, to show that there must be infinitely many primes....<\/p>\n","protected":false},"author":7,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"tags":[151,4,12,49,51],"class_list":["post-361","page","type-page","status-publish","hentry","tag-how-many-primes","tag-medium","tag-other","tag-prime","tag-proof-by-contradiction"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/361","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/comments?post=361"}],"version-history":[{"count":4,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/361\/revisions"}],"predecessor-version":[{"id":1473,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/pages\/361\/revisions\/1473"}],"wp:attachment":[{"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/media?parent=361"}],"wp:term":[{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/math.hmc.edu\/funfacts\/wp-json\/wp\/v2\/tags?post=361"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
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.<\/p>\n\n\n\n
Proving a statement by showing that its negation leads to a contradiction is called a\u00a0proof by contradiction<\/em>.<\/p>\n\n\n\n
Su, Francis E., et al. “How many Primes?.” Math Fun Facts<\/em>. <http:\/\/www.math.hmc.edu\/funfacts>.<\/p>\n\n\n\n
P. Ribenboim, The New Book of Prime Number Records<\/em>, 1996.<\/p>\n\n\n\n
Francis Su<\/p>\n","protected":false},"excerpt":{"rendered":"