3
$\begingroup$

The question is:

Show that $131071=2^{17} - 1$ is prime.

So in this section we have the corollary to a theorem that clearly applies to this question.

Corollary. Any Divisor of $2^p -1$ is of the form $2kp + 1$.

How would you approach this problem?

WHAT I HAVE:

Let $q=2kp +1$ be an odd prime.

Then we have $2^{17} \equiv 1$ (mod q).

Using the a theorem that states that is the order of 2 (mod q) is $t$ then $2^n \equiv 1$ (mod q) iff $t|n$

this implies that $t=1$ or $t=17$

if $t=1$ we have that $2 \equiv 1$(mod q) so $q=1$ obviously impossible since we said $q$ was an odd prime.

So, $t=17$.

Using this I get that $q=131071$ is an odd prime.

$\endgroup$
2
  • $\begingroup$ In your case, the corollary indicates that any possible prime divisor should be of the form $17\times 2k+1=34k+1$. $\endgroup$ Aug 8, 2012 at 0:42
  • $\begingroup$ @anon The theorem states that if $p$ and $q$ are odd primes and $q|a^p -1$, then either $q|a-1$ or $q=2kp + 1$ for some integer $k$. $\endgroup$ Aug 8, 2012 at 0:54

1 Answer 1

4
$\begingroup$

As J.M. noted, any divisor must be of the form $ 34k+1 $. We only have to check potential divisors up to $ \sqrt{131071} \approx 362 $, so only about 10 numbers. You can do this manually relatively quickly. Certain cases can be ruled out quickly like anything ending in a five (35, 205), etc.

$\endgroup$
8
  • 1
    $\begingroup$ There are 10 numbers of that form in this range: 35, 69, 103, 137, 171, 205, 239, 273, 307, 341. 35 and 205 are divisible by 5, while 69, 171, 273 are divisible by 3, 341 is divisible by 11, which leaves 103, 137, 239 and 307. I believe they are all prime. That's still pretty hard to check by hand... $\endgroup$
    – tomasz
    Aug 8, 2012 at 0:55
  • $\begingroup$ I know that :). But I was thinking of approaching the problem a little more elegantly then by trying each divisor. $\endgroup$ Aug 8, 2012 at 0:56
  • 1
    $\begingroup$ @tomasz: You don't have to verify the primality of the divisors; you just have to check to see if they divide $131071$. $\endgroup$
    – tskuzzy
    Aug 8, 2012 at 0:57
  • 2
    $\begingroup$ Howard, there's no elegant reason why $2^{17}-1$ is prime (and, say, $2^{23}-1$ is not); there's no way to avoid doing a certain amount of trial division. Well, there is something called the Lucas-Lehmer test, but that's probably more trouble than it's worth for this particular problem. $\endgroup$ Aug 8, 2012 at 1:17
  • 1
    $\begingroup$ Historical note: Euler proved that $2^{31}-1$ is prime by this restricted trial division (although, he also used that property that divisors of Mersenne numbers are of the form 8n+/-1). He also had access to a list of the primes less than 100,000. (see e.g. my talk slides.) $\endgroup$ Aug 8, 2012 at 4:13

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.