#math trivia #63 solution

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s