The everyday blog of Richard Bartle.
RSS feeds: v0.91; v1.0 (RDF); v2.0; Atom.
3:25pm on Saturday, 28th March, 2009:
Comment
I was thinking about prime numbers the other day, as you do...
The standard proof that there is an infinite number of prime numbers goes something like this. Suppose that there is a finite number of primes. One of these, call it N, must be the last such prime. However, if you multiply all the prime numbers up to and including N together and add 1, you will get a new number which is not divisible by any of those primes. Therefore, there is a prime number larger than N; therefore (because N was not specified) there is an infinite number of such primes.
For example, suppose it was your belief that the largest prime number is 7. Multiply together the prime numbers up to and including 7 (it doesn't matter whether you count 1 as a prime number or not) and you get 2*3*5*7=210. Add 1, and you get 211. Now 211 can not, because of how it was constructed, be divided by 2, 3, 5 or 7, therefore there must be a prime number larger than 7.
Hmm...
211 is itself a prime number, but that's not quite what the proof is saying. All the proof is saying is that there is a larger prime number than the one you thought was the largest — it doesn't say that the number you generated is itself a prime. It's prime with respect to the primes up to and including N, but there could be a prime number between N and (the product of all primes up to N, plus 1).
For example, suppose that instead of multiplying all the primes up to and including N together, we simply took the factorial of N. This has some redundancy in it, in that all the non-primes are the products of primes so their factors would be contributing to the total multiple times, but the basic logic is the same: if you multiply all the counting numbers up to and including N together and add 1, the result can not be divisible by any of those numbers (well, except 1).
Let's try it with 7. 2*3*4*5*6*7=5,040. Add 1 for 5,041. None of the numbers between 2 and 7 inclusive go into 5,041 because they all go into 5,040. Therefore if you think that 7 is the biggest prime number, 5,041 is (accepting only those numbers you believe to be prime) a bigger one.
Except, 5,041 isn't a prime number — it's 71*71. Nevertheless, 71 is still bigger than 7, so your belief that 7 is the largest prime number is still shown to be wrong. The proof correctly shows that there is a prime number larger than N, but it doesn't show that factorial N plus 1 is a prime number: either it is a prime number or there is a prime number smaller than it but larger than N; whatever, N isn't the largest prime number.
In the original example, where you multiply the primes up to and including N together and add 1, we did get a prime number as a result. However, is that always going to be the case? If so, why?
No, it's not. 2*3*5*7*11*13+1=30,031, which has 59 and 509 as factors.
The way the prime-relative-to-primes-up-to-and-including-N number was generated is the specific case of a more general function. For this one, we'll state that 1 counts as a prime number (which is at odds with current thinking, mainly because it makes a mess of the fundamental theorem of arithmetic if 1 isn't a prime, but it satisfies my programmer instincts better).
OK, some notation: let's call the nth prime Pn, starting with P0=1. Let's call the product of all the prime numbers between P0 and Pn inclusive pPn. If, instead of multiplying by one of those primes — call it Pi — we instead add it on at the end, we get (pPn/Pi)+Pi. This will be prime with respect to all the prime numbers up to and including Pn.
Will it always be a prime itself, though?
Well no, we know that from the example with P6=13 above. Nevertheless, for small primes at least, it does a damned good job of generating examples of new primes:
1+2=3
2+1=3
--------
1*2+3=5
1*3+2=5
2*3+1=7
--------
1*2*3+5=11
1*2*5+3=13
1*3*5+2=17
2*3*5+1=31
--------
1*2*3*5+7=37
1*2*3*7+5=47
1*2*5*7+3=73
1*3*5*7+2=107
2*3*5*7+1=211
There's no clear reason why these should be primes, but I think it's probably to do with the restricted range — there aren't enough numbers around for the happy coincidences of multiplication to play a part.
For example, 107 is guaranteed not to be divisible by any of the prime numbers between 1 and 7, but is there anything about this construct that explains why it can't have a factor between 7 and 107? Well yes, there is: the largest value that the smallest prime factor of 107 could take is the largest prime below the square root of 107, which in this example is 7 — we therefore know that any prime factors of 107 must involve at least one prime no larger than 7, and we've accounted for all of those. Once the square roots get less packed, though, it opens up: 2*3*5*7*11+1=2311, so 47 could be a prime factor (it's not, though: 2311 is prime).
None of this is probably of any interest to you at all, or if it is then you probably knew it anyway.
Hey, it was something to think about while I was putting off doing work, though.
Latest entries.
Archived entries.
About this blog.
Copyright © 2009 Richard Bartle (richard@mud.co.uk).