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