# Showing that $2^{17} - 1$ is prime.

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.

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

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.
• @tomasz: You don't have to verify the primality of the divisors; you just have to check to see if they divide $131071$. Aug 8, 2012 at 0:57
• 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. Aug 8, 2012 at 1:17
• 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.) Aug 8, 2012 at 4:13