Given that $n>2$. Prove that if $2^n-1$ is prime then $2^n+1$ is composite or vice versa. I looked on wikipedia on Fermat number and Mersenne prime, but I still don't know how they work.
Asked
Active
Viewed 104 times
3 Answers
2
Hint $\ a\mid (a\!-\!1)^n\!\pm 1\ $ since $ $ mod $\ a\!:\ (a\!-\!1)^n \equiv (-1)^n\equiv \pm 1$
e.g. $\,\ 10\mid 9^n\pm1\, $ is a well-known case (power's of $9$ end with digit $1$ or $9)$
Your case can be viewed as the analogy in radix $\,3.$
Bill Dubuque
- 272,048
1
Clearly you can't prove that $2^n-1$ composite implies $2^n+1$ is prime. Take $n=6$, for example. Going the other way, think about divisibility by $3$.
Ross Millikan
- 374,822
-
I'm not sure what the OP meant by "or vice versa". I suspect they probably meant "and if $2^n+1$ is prime then $2^n-1$ is composite", in other words just the contrapositive of the first statement. – David May 07 '14 at 00:02
-
@David: I took it as "if $2^n-1$ is prime then $2^n+1$ is composite", but I can see your reading as well. I think mine would be the more standard English reading of vice versa. – Ross Millikan May 07 '14 at 00:04
-
Maybe I didn't understand the question right. It asks "Prove that if one of the number 2^n−1 and 2^n+1 is prime, where n>2, then the other is composite." – user148361 May 07 '14 at 00:07
-
Ok, take a look at the pattern of remainders when you divide $2^n-1$ and $2^n+1$ by $3$. Just make a table for small $n$. See if you can find a pattern, then prove it. – Ross Millikan May 07 '14 at 00:13
-
Interesting. Thanks for the help. I'll take a look at the modular route. – user148361 May 07 '14 at 00:21
1
At least one of $2^n-1$ and $2^n+1$ must be divisible by $3$, and neither of them is $3$. Thus, at least one of them is composite.
user2357112
- 2,401