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.
Best Answer
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.