How many prime numbers are there?
Euclid’s theorem is a fundamental statement in number theory which asserts that there are infinitely many prime numbers. There are several well-known proofs of the theorem.
Euclid offered the following proof published in his work Elements (Book IX, Proposition 20) and paraphrased here. Take any finite list of prime numbers p1, p2, …, pn. It will be shown that some additional prime numbers not in this list exist, as follows:
Let P be the product of all the prime numbers: P = p1…pn. Let q = P + 1: 1 more than this product. Then, q is either prime or not. If q is prime then the list is not exhaustive: q is not on it. If q is not prime then some prime factor p divides q. This factor p is not on our list: if it were, then it would divide P (since P is the product of every number on the list); but as we know, p divides P + 1 = q. Then p would have to divide the difference of the two numbers, which is (P + 1) − P or just 1. But no prime number divides 1 so there would be a contradiction, and therefore p cannot be on the list. This means at least one more prime number exists beyond those in the list.
This proves that for any finite list of prime numbers, there is a prime number not on the list. Therefore there must be infinitely many prime numbers.
Related posts:
- How Many Kilometers Are In The Speed of Light
- How Many Elements on the Periodic Table of the Elements Occur Naturally
Tags: Euclid, How Many, infinity, numbers, prime numbers
Add to Favorites
