An observation about Mersenne primes

This post concerns an observation about Mersenne primes. The observation will be made after presenting an example.

Mersenne numbers are integers of the form M_n=2^n-1 where n is a positive integer. If M_n is a prime number, then M_n is said to be a Mersenne primes. Not all Mersenne numbers are prime. Are there infinitely many Mersenne primes? No one has yet been able to resolve this question. As of the writing of this post, there are only 48 known Mersenne primes, the largest of which is M_p where p=57885161, discovered in January 25, 2013. The current largest known Mersenne prime is also the current largest known prime number.

___________________________________________________________________________________________________________________

Example

In this example, p=57885161. Since M_p is prime, it is obviously not divisible by any other prime numbers. In particular, M_p is not divisible by any smaller Mersenne primes. We demonstrate this using congruence modulo arithmetic.

We wish to point out that we are not trying to establish the primality of M_p (doing that would take a great amount of super computing resources). This is merely a simple example of working with Mersenne primes and an exercise in doing congruence modulo calculation.

First, show that M_p=2^p-1 is not divisible by the Mersenne prime 2^{19}-1=524287.

If M_p=2^p-1 is divisible by 2^{19}-1, M_p \equiv 0 \ (\text{mod} \ 2^{19}-1). So we need to show 2^p-1 \not \equiv 0 \ (\text{mod} \ 2^{19}-1) or 2^p \not \equiv 1 \ (\text{mod} \ 2^{19}-1).

Note that 2^{19} \equiv 1 \ (\text{mod} \ 2^{19}-1). So it is a matter of subtracting the largest multiple of 19 out of the exponent p=57885161. We have p=57885161=3046587 \cdot 19+8. We have the following congruence calculation.

    2^{57885161}=(2^{19})^{3046587} \cdot 2^8 \equiv (1)^{3046587} \cdot 2^8=2^8=256 \ (\text{mod} \ 2^{19}-1)

Since 2^p \equiv 256 \ (\text{mod} \ 2^{19}-1) and 256 \ne 1, M_p=2^p-1 is not divisible by 2^{19}-1=524287.

The number 2^{3217}-1 is also a Mersenne prime. To show that M_p=2^p-1 is not divisible by 2^{3217}-1, we only need to show 2^p \not \equiv 1 \ (\text{mod} \ 2^{3217}-1).

Note that 2^{3217} \equiv 1 \ (\text{mod} \ 2^{3217}-1). We have p=57885161=17993 \cdot 3217 + 1680. After subtracting multiple of 3217, we have the remainder 1680. Thus 2^{57885161} congruence modulo 2^{3217}-1 is reduced to 2^{1680} congruence modulo 2^{3217}-1.

    2^{57885161} \equiv 2^{1680} \ (\text{mod} \ 2^{3217}-1)

Since 2^{1680}>1, 2^p \not \equiv 1 \ (\text{mod} \ 2^{3217}-1). Thus M_p=2^p-1 is not divisible by 2^{3217}-1.

___________________________________________________________________________________________________________________

An Observation

The above examples lead to the following observation.

    If a and b are prime numbers such that a<b, then 2^a-1 is not a divisor of 2^b-1.

As in the examples, we need to show 2^b \not \equiv 1 \ (\text{mod} \ 2^a-1). Note that 2^a \equiv 1 \ (\text{mod} \ 2^a-1). According to the division algorithm, we have b=r + a \cdot k where k is some integer and r is the remainder with 0 \le r <a. The remainder r cannot be zero. If it is, a would divide b. But this cannot be since both of them are prime numbers. Since r \ne 0, 2^r>1. We have the following congruence calculation.

    2^b = (2^a)^{k} \cdot 2^r \equiv 2^r \ (\text{mod} \ 2^a-1)

Since 2^r>1, 2^b \not \equiv 1 \ (\text{mod} \ 2^a-1). Thus 2^b-1 is not divisible by 2^a-1.

The above derivation is definitely a much cleaner demonstration than the derivations shown in the above examples.

Another way to state the above statement is that no Mersenne number can be divisible by any smaller Mersenne number.

Note that in the above statement, 2^a-1 and 2^b-1 do not need to be primes. Only the exponents a and b need to be primes. There are many Mersenne numbers that are not prime numbers. The smallest is 2^{11}-1=28*89. Other smaller non-prime Mersenne numbers are 2^{23}-1 and 2^{29}-1.

So the above statement says that even when a Mersenne number is composite, it cannot have factors of the form 2^a-1. It can certainly not have factors in the form of a Mersenne prime. In testing whether 2^b-1 is a prime, it can be safe to skip any smaller number of the form 2^a-1. This fact could be useful in testing the primality of a Mersenne number (at least marginally useful).

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Advertisements

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