# Prime number proof

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.

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.$

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$.

• 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 7 '14 at 0: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 7 '14 at 0: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 7 '14 at 0: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 7 '14 at 0:13
• Interesting. Thanks for the help. I'll take a look at the modular route. – user148361 May 7 '14 at 0:21

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.

• As simple and short as that. +1 – DonAntonio May 7 '14 at 4:05