Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
In your case, the corollary indicates that any possible prime divisor should be of the form $17\times 2k+1=34k+1$. –  J. M. Aug 8 '12 at 0:42
    
@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$. –  HowardRoark Aug 8 '12 at 0:54

1 Answer 1

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.

share|improve this answer
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... –  tomasz Aug 8 '12 at 0:55
    
I know that :). But I was thinking of approaching the problem a little more elegantly then by trying each divisor. –  HowardRoark Aug 8 '12 at 0:56
1  
@tomasz: You don't have to verify the primality of the divisors; you just have to check to see if they divide $131071$. –  tskuzzy Aug 8 '12 at 0:57
    
@tomasz, 341 is obviously divisible by 11. –  Rick Decker Aug 8 '12 at 0:57
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. –  Gerry Myerson Aug 8 '12 at 1:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.