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.

  • 5
    $\begingroup$ 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. $\endgroup$ – Daniel Fischer Jul 25 '13 at 17:20
  • 3
    $\begingroup$ Just found : math.stackexchange.com/questions/402603/… $\endgroup$ – lab bhattacharjee Jul 25 '13 at 18:22
  • 1
    $\begingroup$ This is not a duplicate. This is a "check my proof" question, which cannot be a duplicate! $\endgroup$ – user1729 Jul 26 '13 at 9:49
  • $\begingroup$ (As a side point, your proof is fine.) $\endgroup$ – user1729 Jul 26 '13 at 9:50
  • $\begingroup$ @user1729: that's right. So, how can I recall my "close" vote? $\endgroup$ – mau Jul 26 '13 at 10:04

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

| 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

| cite | improve this answer | |

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.