# How to check if Mersenne number is prime?

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.

• Search for "Lucas-Lehmer test". – Daniel Fischer Jun 25 '13 at 13:13

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

• 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 – Stefan4024 Jun 25 '13 at 13:31
• 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. – Daniel Fischer Jun 25 '13 at 13:34
• Can you chech the edit I made? – Stefan4024 Jun 25 '13 at 13:41
• 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$). – Daniel Fischer Jun 25 '13 at 14:36
• 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. – Daniel Fischer Jun 25 '13 at 14:46