I used to assume that was because the binary epresentation of such a number consists entirely of 1's so that the number could easily be generated in instalments in a computer, but while browsing through Hardy and Wright's Introduction to the Theory of Numbers, I came upon another relevant fact.
For some Mersenne numbers there is a very short short cut to finding whether they are prime.
If the prime p is greater than 7, and of the form 4n + 3, that is if it leaves remainder 3 when divided by 4, then:
if 2p + 1 is prime, that number is a factor of 2^p - 1, otherwise 2^p - 1 is prime.
So, for example, to check whether or not 2^19 - 1 is prime, consider 2*19 + 1 = 39
39 is not prime, therefore 2^19 - 1 is prime.
To check whether or not 2^251 - 1 is prime, consider 2*251 + 1 = 503; that is prime and is therefore a factor of 2^251 - 1 which is therefore not prime.
Next time you hear of the discovery of a large prime of the form 2^p - 1, check to see if p leaves remainder 3 when divided by 4; I bet it will.
Posts
