Euclid's Proof that there are an Infinite Number of Primes06 Mar 2016
Proving these results from classic number theory are useful for many reasons. For one, they prepare you for the study of cryptography. It never hurts to study cryptography now does it? Second, they are fun and interesting to boot. The latter reason is enough if you ask me.
They are also nice simple proofs to improve our proof writing skills (in other words, our so-called mathematical maturity). You’ve probably heard me say that term before. It sounds pretentious doesn’t it? However, it’s just learning how to be more comfortable with higher math. I believe anyone that applies themselves can learn higher math. It just takes work and patience. Like learning a musical instrument, with practice, you will get better. So let’s start busting this out.
This is one of the most celebrated proofs, in all of mathematics, and Euclid is also one of the most celebrated mathematicians in history. At its heart, the proof is rather simple, yet at the same time it is rather profound. Euclid, a Greek mathematician, did the proof around 300 B.C.
The proof involves generating a contradiction; a rather important proof technique that, at first, can seem a bit counter-intuitive. To this day, it stands as one of the most important theorems in number theory. I would gather the fundamental theorem of arithmetic ranks higher in importance, but guess who fathered that proof as well? That’s right, Euclid!
He was rather productive, those many eons ago, before social media and YouTube could distract him. There are numerous other related theorems, involving prime numbers, and many problems are still open today.
So, let’s begin with this delicious gem.
Quick definition: a prime number is a number that is divisible by only itself (no remainder) and 1. Convention is that the first prime starts at 2 - i.e., 1 doesn't count.
The theorem basically says if one tries to list all the primes from 2,3,5….n, the list will not contain all the prime numbers - it will be incomplete. That is there will be more prime numbers after n. More specifically it says there are actually an infinite number of primes. Hence, there is no largest prime number.
To show there are an infinite number of primes we will find a contraction. To do that let’s assume there is actually just a finite number of primes \(P_1, P_2, P_3…P_n\). Let \(P=P_1P_2P_3…P_n+1\). From the fundamental theorem of arithmetic, we know that P is either prime or can be composed of prime factors (i.e., is composite).
For the case where P is prime, it must be a prime number larger than \(P_n\) since no term of \(P_1, P_2,P_3…P_n\) could be a factor of P since there would be a non-zero remainder, and hence, this is contradiction to our assumption. Why? Since our assumption that there are a finite number of primes was shown to be false by contraction.
For the second case, where the number P is a composite, we know that there must be prime factors of P. However, as in the first case, none of those prime factors can include \(P_1,P_2,P_3…P_n\) as there would be a non-zero remainder.
Hence, the assumption that there is a finite number of primes is false since both cases where P is either prime or composite have been shown to be a contradiction. Hence, this proves that there are not a finite number of primes. This can be said more simply as there must be an infinite number of primes - this results from just negating the prior sentence.
Some easier proofs regarding prime numbers are that 2 is the only even prime number, and 2 and 3 are the only consecutive prime numbers, among many others.
Soon, I will post some code that performs numerical prime number analysis (probably just in C). Maybe we will be able to crack some encryption codes, which are based in large prime numbers - probably not. Do you think the NSA is reading my blog?