# Find the Least Prime Divisor of $2^{17}-1$

Show that the least prime divisor of $2^{17}-1$ is $2^{17}-1$ itself.

This question is really anoying. Let $N=2^{17}-1$. What I know is that if $q\mid N$, then $q=34k+1$ for some $k \in \Bbb{N}$ and $q \equiv \pm1 \pmod 8$. Therefore,

$$q \equiv 2k+1 \equiv \pm1 \pmod 8$$

We get $k \equiv -1, 0 \pmod 4$. So $q=136x+1$ or $q=136x-33$ for some $x \in \Bbb{N}$.

This is all I know about finding the prime divisor of the form ${2^{p}-1}$, which might be the Mersenne number. But do I have to just substitute each possible value of $q$ into $N$ in order to show that it ultimately doesn't have any prime divisors other than $N$ itself? It takes so much time and effort. And I don't think the problem is just to make students tediously substitute each case one by one(if it is, then I'm so frustrated).

So the question: is there any more time-saving way to distinguish certain types of Mersenne number without goint too far from my basic understading of Number Theory? Or should I just subsitute one by one and that's the best choice I can take?

Thanks!

Edited This was a question that baffled me about few months ago, and after studying the case for perfect numbers, now I do know that $2^{17}-1$ is a Mersenne number(related to the perfect number $8589869056$). But I still think just memorizing the case doesn't give me full insight into this area.

• Testing that $2^n-1$ is prime is hard, that's why GIMPS exists. – vadim123 Nov 10 '13 at 0:37
• If you are dealing with large Mersenne numbers, there is the Lucas-Lehmer test which is the process used to establish many of the prime number records in recent decades. – Old John Nov 10 '13 at 0:42
• @vadim123 Wow, what is that site exactly for? An association for sharing knowledge to find Mersenne number? – Taxxi Nov 10 '13 at 0:46
• GIMPS has a screen saver you can install that will use your computer's spare processing power to look for Mersenne primes. For over a decade, the record for largest known prime has been held by someone running this software. See here. – vadim123 Nov 10 '13 at 0:50
• There is always lots to learn :-)! See: mathworld.wolfram.com/PrattCertificate.html. Here is the example they use on that web site and I posted the certificate for your particular problem, so you can follow: {True, {7919, 7, {2, {37, 2, {2, {3, 2, {2}}}}, {107, 2, {2, {53, 2, {2, {13, 2, {2, {3, 2, {2}}}}}}}}}}}. Regards – Amzoti Nov 10 '13 at 0:58

Let $p|2^{17} - 1$, then we have $2^{17} \equiv 1 \pmod p$, but we also have from Fermat's Little Theorem $2^{p-1} \equiv 1 \pmod p$.

From Lagrange Theorem for group order we get that $2^{\gcd(p-1,17)} \equiv 1 \pmod p$.

Obivously the greatest common divisor is $17$, because otherwise (if the gcd were $1$) then $2 \equiv 1 \pmod p$, which is impossible.

Then we have $17 \mid p-1$ and because $p-1$ is even we have $34\mid p-1$. So we need to check all prime numbers of the form $p=34k + 1 \quad \forall k \in \mathbb{N}$ such that $p \in (1,\sqrt{2^{17} - 1}]$. Which reduces the number of divisors to check. Actually there are just $4$ primes in this inteval, those are $103, 137, 239, 307$. You can check that none of them divides $2^{17} - 1$, implying that $2^{17} - 1$ is prime.

Also you can check how Euler proved that $2^{31} - 1$ is prime, and apply the same method on $2^{17} - 1$.

Actualy $2^{17} - 1 = 131071$ isn't that big number, even without knowledge in number theory it isn't so much hord work to do.

And at last as other users have suggested use Lucas-Lehmer Test.

• Oh, I forgot about the Sieve of Erastosthenes... Thanks for the link, too. – Taxxi Nov 10 '13 at 2:16
• @TaxxiDriver Hope it helps ;) As I said the first method can be useful and quite fast for small numbers, but for big numbers the Lucas-Lehmer Test will do the job much better – Stefan4024 Nov 10 '13 at 2:22
• According to most lists of Mersenne numbers, the number $2^{17}-1$ was first proven prime by Cataldi in 1588. This illustrates that this can be done by "brute force", without knowing that factors of Mersenne numbers must have a special form. Just like you said. – Jeppe Stig Nielsen Dec 21 '14 at 16:25
• @Sky If p has a divisor greater than $\sqrt{2^{17} - 1}$ then it also must have one smaller than $\sqrt{2^{17} - 1}$. So if there exist such a divisor, then we must find it's "partner(s)" in the given interval. But since $2^{17} - 1$ doesn't have a divisor in the interval, it implies it also doesn't have one in $(\sqrt{2^{17} - 1}, 2^{17}-1)$. Obviously this greatly reduces the numbers we need to check. – Stefan4024 Jun 22 '15 at 10:48
• Yeah, I got confused, and though we were dealing with $2^{19}-1$. @Stefan4024 – Thomas Andrews Oct 6 '16 at 23:17