Euclid’s Proof of the Infinitude of Primes
So a few weeks ago my younger sister asked me what the biggest prime number was. I was getting prepared to explain Euclids proof to her… when I realised that she probably doesn’t care and also didn’t exactly need to know about it, instead I just told her that “it’s a pretty large number”. Truth is, there is no largest prime number as much as there is no largest number. Euclid proved this in around 300 BC, which is also the oldest known proof that there are infinite number of primes.
Euclid started by looking at the known primes and adding one to their product. For example both 2 and 3 are primes: their product plus 1 is also a prime: 2*3+1=7. Continue by adding 5 to the same process: 2*3*5+1=31 – and voir la, that is a prime too. The nice but not beautiful thing about this is that sometimes this algorithm will churn out primes and sometimes it will not!
Here is another way of looking at it:
Suppose that p1=2 < p2 = 3 < … < pr are all of the primes. Let P = p1p2…pr+1 and let p be a prime dividing P; then p can not be any of p1, p2, …, pr, otherwise p would divide the difference P–p1p2…pr=1, which is impossible. So this prime p is still another prime, and p1, p2, pr would not be all of the primes
Although Euclid did not find the way to using this procedure to find only primes, he did find that this can be used to show that there is infinitely many primes.