# Why do Mersenne primes only have prime inputs?

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$. – Lord Shark the Unknown Dec 29 '17 at 13:45
• – lab bhattacharjee Dec 29 '17 at 13:46
• Okay but could you elaborate a bit more? – Mohammad Zuhair Khan Dec 29 '17 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 '17 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$. – reuns Dec 29 '17 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}
• 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. – Mohammad Zuhair Khan Dec 29 '17 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.$