CACTUSPEAR.ORG PRESENTS

mersenne primes

Mersenne primes, named after the French mathematician Marin Mersenne (1588-1648), are prime numbers of the form 2p−1, where p is prime.

Some examples are 3 = 22−1, 7 = 23−1, 31 = 25−1, and so on. Not all numbers of the form 2p−1 are prime. For example, 2047 = 211−1 = 23 * 89, is not prime.

For fun, we'll show that any number of the form 2m−1, where m is a composite number, cannot be prime. That is, if a number of the form 2m−1 is prime, then m is prime.

Proof: Let m = ab, where a and b are integers greater than 1. We use the identity xn−1 = (x−1)(xn−1 + xn−2 + ··· + 1).

So we have 2m−1 = 2ab−1 = (2a)b−1, which is divisible by 2a−1, and we are done.

Note: One consequence of the above result is that we could have defined a Mersenne prime equally well as any prime of the form 2n−1, where n is an integer.

Source: wikipedia.org

Note: To prove the identity, we have

(x−1)(xn−1 + xn−2 + ··· + 1) = (x−1)Σn−10xk = xΣn−10xk − Σn−10xk

Let's examine more closely the first term of the final expression above:

n−10xk = Σn−10xk+1

= Σn1xk

= xn + Σn−11xk

= xn + Σn−10xk − 1

Finally, we have (x−1)(xn−1 + xn−2 + ··· + 1) = xΣn−10xk − Σn−10xk

= xn + Σn−10xk − 1 − Σn−10xk = xn−1


cactuspear home
comments to comments at cactuspear dot org