Big Prime Numbers

When big pimes are discovered, they are always Mersene numbers, of the form 2^p - 1 for p prime.

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.