# 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$. – 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
Oops I misread. – anon Aug 8 '12 at 1:05

## 1 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.

-

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
show 3 more comments
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 29, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9456146359443665, "perplexity_flag": "head"}