0
$\begingroup$

How can I prove that that Mersenne number, number of the type $2^n - 1$ is prime number. One theorem says that if $2^n - 1$ is prime than $n$ is prime number also. But this doesn't work vice versa. For example: $2^{11} - 1$ isn't prime number, although $n = 11$ which is prime number. Is there any way how can I check whether $2^{17} - 1, 2^{23} - 1, 2^{31} - 1 ...$ are primes or not?

Here's one way i find, although I need an explanation:

For $2^{17} - 1$

Let there be $p|2^{17} - 1$

By Fermat theorem we have $p|2^{p-1} - 1$

So $p|2^{lcm(17,p-1)} - 1$ (WHY????)

Least common multiplier can be either 1 or 17. Obviously it's 17. So we have that

$17|p-1$ and $2|p-1$ which is true for every prime number bigger than 2.

Finally we get $34|p-1$ and $p=34k + 1$

Because p is divisor of $2^{17} - 1$ it means it's smaller or equal to $\sqrt{2^{17} - 1}$

Number that satisfy both conditions are {103, 137, 239, 307} (shouldn't I check all numbers in the range of $\sqrt{2^{17} - 1}$ and $2^{17} - 1$? Because $p$ can be in that range) and none of them divides $2^{17} - 1$. Which means that $2^{17} - 1$ is prime.

$\endgroup$
  • $\begingroup$ Search for "Lucas-Lehmer test". $\endgroup$ – Daniel Fischer Jun 25 '13 at 13:13
1
$\begingroup$

To the best of my knowledge, the best known test to determine whether a Mersenne number is prime is the Lucas-Lehmer test. If you already know that $p$ is an odd prime (it doesn't work for $M_2 = 3$), let

$U_0 = 4$, and $U_{n+1} \equiv U_n^2 - 2 \pmod {M_p}$.

Then $M_p$ is prime if and only if $U_{p-2} \equiv 0 \pmod {M_p}$.

Taking the modulus at each step, to check the primality of $M_p$, only $2\cdot p$-bit numbers are necessary, thus the proof (or disproof) is computationally feasible even for larger $p$.

The mathematics behind that are more involved than I am ready to explain here.


Regarding the edit - I presume the most important thing is the line with the "why?".

For the assumed prime $p$ dividing $M_{17}$, let $k$ be the order of 2 in $\mathbb{Z}_p^\ast$ (the group of units [non-zero elements] of $\mathbb{Z}_p$).

Then $p \mid 2^n - 1 \iff 2^n \equiv 1 \pmod p \iff k \mid n$. The last can be seen by writing $n = q\cdot k + r\quad, 0 \leqslant r < k$.

So by assumption $k \mid 17$, and by Fermat's theorem, $k \mid (p-1)$. Hence $k \mid (17, p-1)$.

Because $p$ is divisor of $2^{17}−1$ it means it's smaller or equal to $\sqrt{2^{17}−1}$

That's not quite correct as stated, but assuming $M_{17}$ composite, and $p$ its smallest prime divisor, the conclusion $p \leqslant \sqrt{2^{17}-1}$ holds. (Since $M_p \equiv 3 \pmod 4$, we can replace the $\leqslant$ with a $<$.)

$\endgroup$
  • $\begingroup$ The proof isn't important, what I'm more interested is the method. The Lucas-Lehmer test isn't that simple, for example if p = 31, then $U_{p-2}$ is a huge number. Using modulo operation for base $M_p$ it can be shortend, but still you need to do a lot of calculations $\endgroup$ – Stefan4024 Jun 25 '13 at 13:31
  • 1
    $\begingroup$ But you take the modulus at each step. For $p = 31$, you are fine with 64-bit numbers, that's no problem. It even only takes a few minutes (well, perhaps a few more) doing it by hand. For $M_p$ you need $2 \cdot p$-bit numbers for the intermediate results, that's not terrible. $\endgroup$ – Daniel Fischer Jun 25 '13 at 13:34
  • $\begingroup$ Can you chech the edit I made? $\endgroup$ – Stefan4024 Jun 25 '13 at 13:41
  • 1
    $\begingroup$ The smallest prime divisor of a composite number is always $\leqslant$ the square root. Let $n = a\cdot b$ with $1 < a \leqslant b$ (hence $a \leqslant \sqrt{n}$). If $a$ is prime, we know one prime divisor of $n$ which is $\leqslant \sqrt{n}$. If $a$ is composite, take any prime divisor $p$ of $a$. Then $p < a \leqslant \sqrt{n}$. So in either case, we know that $n$ has a prime divisor $\leqslant \sqrt{n}$. Hence the smallest prime divisor of $n$ is $\leqslant \sqrt{n}$. But that doesn't mean that every prime divisor of $n$ is $\leqslant \sqrt{n}$ (consider $M_{11} = 23 \cdot 89$). $\endgroup$ – Daniel Fischer Jun 25 '13 at 14:36
  • 1
    $\begingroup$ And then the conclusion $p < \sqrt{M_q}$ need not hold. But, every composite $n$ has a smallest prime divisor. That must be $\leqslant \sqrt{n}$. So if you also know that all prime divisors of $n$ must have some special form (here $\equiv 1 \pmod {34}$), and you don't find a divisor of $n$ among the primes $\leqslant \sqrt{n}$ having the required form, you know that $n$ is in fact prime. $\endgroup$ – Daniel Fischer Jun 25 '13 at 14:46

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.