Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to prove that not both integers $2^n-1,2^n+1$ can be prime for $n \not=2$. But I am not sure if my proof is correct or not:

Suppose both $2^n-1,2^n+1$ are prime, then $(2^n-1)(2^n+1)=4^n-1$ have 2 precisely two prim factors. Now $4^n-1=(4-1)(4^{n-1}+4^{n-2}+ \cdots +1)=3A$. So one of $2^n-1, 2^n+1$ must be 3. which implies $n=1$ or $n=2$ (rejected by assumption). Putting $n=1$, we have $2^n-1=1$ which is not a prime. Hence the result follows.

I also wanna know if there is alternative proof, thank you so much.

share|cite|improve this question
There is an alternative proof, $2^n - 1$ can only be prime if $n$ is prime, $2^n + 1$ can only be prime if $n$ is a power of $2$. And yes, your proof is correct. – Daniel Fischer Jul 25 '13 at 17:20
Just found :… – lab bhattacharjee Jul 25 '13 at 18:22
This is not a duplicate. This is a "check my proof" question, which cannot be a duplicate! – user1729 Jul 26 '13 at 9:49
(As a side point, your proof is fine.) – user1729 Jul 26 '13 at 9:50
@user1729: that's right. So, how can I recall my "close" vote? – mau Jul 26 '13 at 10:04
up vote 66 down vote accepted

Of the three consecutive integers $2^n-1,2^n,2^n+1$, one must be divisble by 3, and it can't be $2^n$.

share|cite|improve this answer

If $n$ is even $=2m,2^n-1=2^{2m}-1=4^m-1$ is divisible by $4-1=3$ and $4^m-1>3$ if $m\ge1\iff n\ge2$

If $n$ is odd $=2m+1,2^n+1=2^{2m+1}+1$ is divisible by $2+1=3$ and $2^{2m+1}+1>3$ if $m\ge1\iff n\ge3$

alternatively, $$(2^n-1)(2^n+1)=4^n-1$$ is divisible by $4-1=3$

So, at least one of $2^n-1,2^n+1$ is divisible by $3$

Now, $2^n+1>2^n-1>3$ for $n>2$

$\implies $ for $n>2,$ one of $2^n-1,2^n+1$ must be composite

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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