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!

  • $\begingroup$ If $m$ is a factor of $n$, then $2^m-1$ is a factor of $2^n-1$. $\endgroup$ – Lord Shark the Unknown Dec 29 '17 at 13:45
  • $\begingroup$ See en.wikipedia.org/wiki/Mersenne_prime $\endgroup$ – lab bhattacharjee Dec 29 '17 at 13:46
  • $\begingroup$ Okay but could you elaborate a bit more? $\endgroup$ – Mohammad Zuhair Khan Dec 29 '17 at 13:46
  • $\begingroup$ 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). $\endgroup$ – lulu Dec 29 '17 at 13:51
  • $\begingroup$ 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$. $\endgroup$ – 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}

  • $\begingroup$ Thanks for the explanation! $\endgroup$ – Mohammad Zuhair Khan Dec 29 '17 at 13:50
  • $\begingroup$ @MohammadZuhairKhan DId you ever ask to one of your teachers why this is true? $\endgroup$ – José Carlos Santos Dec 29 '17 at 13:52
  • $\begingroup$ 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. $\endgroup$ – 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.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.