# Why Do Mersenne Primes Only Occur at Terms of Prime Index?

A Mersenne prime is a prime of the form $2^n-1$.
Only when $n$ is a prime itself is there a chance that $2^n-1$ is a Mersenne primes. The largest primes discovered are almost always Mersenne primes. Some of the more known Mersenne primes are $3, 7, 31, 127$, e.t.c.
Now on to the question.

Why do non-prime values of $n$ never yield a prime?

I have always heard from my teachers that Mersenne primes occur at only the prime values of $n$ but no one ever explained it to me. Is there any way of proving this? Or are there any exceptions for $n>1$?

P.S. As you may have guessed from my writing "teachers" instead of "professors", I am only in grade $10$ and not that skilled so I would prefer if you could give me simple explanations. Thanks in advance!

• If $m$ is a factor of $n$, then $2^m-1$ is a factor of $2^n-1$. Dec 29, 2017 at 13:45
• Dec 29, 2017 at 13:46
• Okay but could you elaborate a bit more? Dec 29, 2017 at 13:46
• As a related exercise, you might try to prove that if $2^k+1$ is prime then $k$ must be a power of $2$. This one dates back to Fermat who conjectured (well, guessed really) that $2^{2^n}+1$ was always prime. This turned out to be very wrong (in fact, Fermat knew the same list of so-called Fermat primes that we know today. Not one new prime of that form has been found).
– lulu
Dec 29, 2017 at 13:51
• A good exercice is to show that $\gcd(2^n-1, 2^m-1) = \gcd(2^n-2^m, 2^m-1)= \gcd(2^{m}(2^{n-m}-1), 2^m-1)$ $=\gcd(2^{n-m}-1, 2^m-1)$ looks like one step of the usual $\gcd$-Euclid algorithm, so that $\gcd(2^n-1, 2^m-1) = 2^{\gcd(n,m)}-1$. Dec 29, 2017 at 14:13

Because if $m=kl$, with $k,l>1$, then\begin{align}2^n-1&=2^{kl}-1\\&=(2^k)^l-1^l\\&=(2^k-1)\bigl((2^k)^{l-1}+(2^k)^{l-2}+\cdots+1\bigr).\end{align}

• Thanks for the explanation! Dec 29, 2017 at 13:50
• @MohammadZuhairKhan DId you ever ask to one of your teachers why this is true? Dec 29, 2017 at 13:52
• Well I never did as I am not supposed to be studying its properties for another couple of years. He only told that Mersenne primes only occur when $n$ is prime when he was explaining prime numbers while solving a probability question. Dec 29, 2017 at 13:56

I think that this is easiest seen when numbers are represented in binary form. A number $2^n - 1$ is the represented as $n$ ones, e.g. $255 = 2^8 - 1 = 11111111_2.$ When $n$ is not a prime, this number can be grouped into subparts, e.g. $1111~1111_2$ or $11~11~11~11_2$, and then easily be written as a product: $1111_2 \times 1~0001_2$ or $11_2 \times 1~01~01~01_2.$

That is because of theory pertaining to the family of Lucas sequences, which the sequence of Mersenne numbers is a member of. in particular, and applied here to the sequence of Mersenne numbers, $$M_{n},$$:

$$M_{r} | M_{s} \,\,\,\, if \,\, and \,\, only \,\, if \,\,\,\, r | s.$$

Hence, if the index of some Mersenne prime was composite, say $$mn$$, then this would lead to a contradiction because $$M_{mn}$$ would then be divisible by both $$M_{n}$$ and $$M_{m}$$ contrary to the assumption that it is prime.