# 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, 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 . 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}$