2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David May 7 '14 at 0:02
  • $\begingroup$ @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. $\endgroup$ – Ross Millikan May 7 '14 at 0:04
  • $\begingroup$ 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." $\endgroup$ – user148361 May 7 '14 at 0:07
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan May 7 '14 at 0:13
  • $\begingroup$ Interesting. Thanks for the help. I'll take a look at the modular route. $\endgroup$ – user148361 May 7 '14 at 0:21
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.