Subscription

Books
Shop
About

Wednesday, July 31, 2013

How many prime numbers are there?

That's easy - infinitely many. 
Well, you know there are infinitely many counting numbers (also known as natural numbers) right?  I remember watching this kiddies activity video in the eighties and they had a song "...you can count forever, there'll always be one more..." and the doubter would say when you named the next really big number, "add one to it!"  You could always add one, ergo, there is no largest or maximum counting number.  

But how does one know that there is no largest PRIME number? 

Long term, there are many more non-primes than primes, that is the prime numbers appear less and less frequently.  Think about it: start counting from 1, 2, ... at first half the numbers are non-prime (all the even numbers.)  After 3, all the factors of three are non-prime too.  That is, from then on, not only all the even numbers, but also all the odd numbers divisible by three, will be non-prime.  And so on. To be prime, a number q will have to pass the test: not divisible by 2, not a factor of 3, not a factor of 4 (implied already since 4 is made up of 2's), not a factor of 5, ... AND not a factor of any other number smaller than itself (although we can stop testing when we reach half of the number or q/2 since no larger number - larger than q/2 and smaller than q - will divide q evenly anyway)
Here's a picture of how the factors eliminate the primes, and so the occurrence of primes is not as random as one might first think, at least if one takes a different point of view: that the occurrence of non-primes is extremely regular, beat beat beat beat - can you hear the music? 

Exactly how infrequently the prime numbers occur "over time" - as the numbers get bigger - is a cool question.  We'll come back to it later. 

Maybe the picture is enough to convince you that there is no largest prime number, that no matter how large/high you go there is always a loose end, a number q that hasn't been captured by any of the wanna-be factors in the 2 to q/2 range. 

If that is not convincing enough, in the next post (or two) we'll derive a good estimate for the difference between two consecutive prime numbers.  So, we are assured that if you add "difference" to a prime number, then we'll get the next largest one.  That is to say, "there'll always be one more!"

My Other Blogs

About Me

Followers