4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Testing that $2^n-1$ is prime is hard, that's why GIMPS exists. $\endgroup$ – vadim123 Nov 10 '13 at 0:37
  • 1
    $\begingroup$ 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. $\endgroup$ – Old John Nov 10 '13 at 0:42
  • $\begingroup$ @vadim123 Wow, what is that site exactly for? An association for sharing knowledge to find Mersenne number? $\endgroup$ – Taxxi Nov 10 '13 at 0:46
  • 1
    $\begingroup$ 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. $\endgroup$ – vadim123 Nov 10 '13 at 0:50
  • 1
    $\begingroup$ 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 $\endgroup$ – Amzoti Nov 10 '13 at 0:58
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Oh, I forgot about the Sieve of Erastosthenes... Thanks for the link, too. $\endgroup$ – Taxxi Nov 10 '13 at 2:16
  • $\begingroup$ @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 $\endgroup$ – Stefan4024 Nov 10 '13 at 2:22
  • $\begingroup$ 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. $\endgroup$ – Jeppe Stig Nielsen Dec 21 '14 at 16:25
  • 1
    $\begingroup$ @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. $\endgroup$ – Stefan4024 Jun 22 '15 at 10:48
  • 1
    $\begingroup$ Yeah, I got confused, and though we were dealing with $2^{19}-1$. @Stefan4024 $\endgroup$ – Thomas Andrews Oct 6 '16 at 23:17

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.