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.

  • 0
    In your case, the corollary indicates that any possible *prime* divisor should be of the form $17\times 2k+1=34k+1$.2012-08-08
  • 0
    @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$.2012-08-08

1 Answers 1

4

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.

  • 1
    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...2012-08-08
  • 0
    I know that :). But I was thinking of approaching the problem a little more elegantly then by trying each divisor.2012-08-08
  • 1
    @tomasz: You don't have to verify the primality of the divisors; you just have to check to see if they divide $131071$.2012-08-08
  • 0
    @tomasz, 341 is obviously divisible by 11.2012-08-08
  • 0
    @tskuzzy: Yup, but if you don't do an easy prime sieve, you have to do even more work dividing, which is my point. ;)2012-08-08
  • 0
    @tomasz: Well I divide better than I sieve :P2012-08-08
  • 2
    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.2012-08-08
  • 0
    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](https://sites.google.com/site/rknmodn/talks/tk240407.pdf).)2012-08-08