Burt Kaliski Jr. (@modulomathy)

3/3/12 5:08 PM

#math trivia for #March3: #63 is not a #Mersenne prime but it’s divisible by two of them. Which ones? (Mersenne p = 2^q-1, p, q prime.)

The day’s number, 63, has the form 2^6-1, but neither the exponent 6 nor the number 63 is prime.

However, both prime factors of 63, 3 and 7, are Mersenne:

3 = 2^2 – 1

7 = 2^3 – 1

In order for a number p of the form 2^q-1 to be prime, it’s necessary for q to be prime. Suppose that q is not prime. Then it can be expressed as q = r*s where r, s >; 1. As a result, 2^r-1 will divide p, so p won’t be prime. (To see the divisibility, let x = 2^r, and recall that x^s-1 can be factored into x-1 and x^(s-1)+x^(s-2)+…+x+1.)

Although necessary, q being prime isn’t sufficient for p to be prime. The smallest prime q for which p is not prime is q = 11. Mersenne primes do occur occasionally among numbers of the form 2^q-1 where q is prime, but not always, and never when q is not prime.

### Like this:

Like Loading...

*Related*