2
$\begingroup$

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!

$\endgroup$
5
  • 2
    $\begingroup$ If $m$ is a factor of $n$, then $2^m-1$ is a factor of $2^n-1$. $\endgroup$ Dec 29, 2017 at 13:45
  • $\begingroup$ See en.wikipedia.org/wiki/Mersenne_prime $\endgroup$ Dec 29, 2017 at 13:46
  • $\begingroup$ Okay but could you elaborate a bit more? $\endgroup$ Dec 29, 2017 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, 2017 at 13:51
  • 2
    $\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, 2017 at 14:13

3 Answers 3

6
$\begingroup$

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}

$\endgroup$
3
  • $\begingroup$ Thanks for the explanation! $\endgroup$ Dec 29, 2017 at 13:50
  • $\begingroup$ @MohammadZuhairKhan DId you ever ask to one of your teachers why this is true? $\endgroup$ Dec 29, 2017 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$ Dec 29, 2017 at 13:56
6
$\begingroup$

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.$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .