Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

For any $n>2$, among $2^n-1$ and $2^n+1$, at most one is prime.

I have no clue :(

share|cite|improve this question
up vote 33 down vote accepted

One of the three consecutive integers $(2^n-1)$, $2^n$, and $(2^n+1)$ is a multiple of 3. It's not $2^n$, so one of $2^n-1\,$ and $2^n+1\, $ is a multiple of three (and $\neq 3$), so at most one of them is prime.

share|cite|improve this answer

As $(2^n-1),2^n,(2^n+1)$ are three consecutive integers, exactly one of them is divisible by $3$

Now, $(2,3)=1\implies 3\mid(2^n-1)(2^n+1)$

which can also proved as $(2^n-1)(2^n+1)=4^n-1^n$ which is divisible by $4-1=3$ as $(a-b)\mid(a^m-b^m)$ where $m$ is any natural number.

So, exactly one of them is divisible by $3$, hence is composite as $n>2, 2^n-1>3$ so is $2^n+1$

In fact $3\mid(2^n+1)$ if $n$ is odd as $(a+b)\mid(a^{2m+1}+b^{2m+1})$ (where $m$ is any natural number)

and $3\mid(2^n-1)$ if $n$ is even as we have just proved $3\mid (4^m-1)\implies 3\mid(2^{2m}-1)$

A little generalization: for $(a^n-1)a^n(a^n+1)$ where natural number $n>1$

Now, (i) $(a-1)\mid(a^n-1)$ so $(a^n-1)$ will be composite if $a-1>1\implies a>2$

Again, as Marvis has observed, if $n$ is composite $=c\cdot d$(say), $(a^c-1)\mid(a^n-1)$

So, the necessary condition for $a^n-1$ to be prime is $a=2,n$ is prime $=p$(say), so that $a^n-1$ becomes $2^p-1$(Mersenne numbers)

(ii) $a^n+1$ will be even, hence composite if $a>1$ is odd.

Again, if $n$ is odd $=e(2f+1)$(say) where $e,f$ are natural numbers, $(a^e+1)\mid(a^n+1)$

So, the necessary condition for $a^n+1$ to be prime is $a$ is even, $n$ does not have any odd factor, so that $a^n+1$ becomes $(2m)^{2^r}+1$

If $m=1,$ it becomes $2^{2^r}+1$(Fermat number)

So, $a^n+1,a^n-1$ both can be prime if $a=2, p=2^r\implies r=1,p=2$

share|cite|improve this answer
It is, of course, easy to determine which of $2^n+1$ and $2^n-1$ is divisible by $3$, by noting that $2\equiv -1\pmod 3$. – Thomas Andrews Dec 20 '12 at 18:51
isnt this solution too complicated? – Carry on Smiling Dec 20 '12 at 19:15
@Khromonkey, have you seen the generalization? – lab bhattacharjee Dec 23 '12 at 3:54

If $n$ is composite, then $2^n-1$ is also composite. (Since $2^{ab} - 1 = (2^a - 1)M$).

If $n$ is a prime, and since $n>2$, we have that $n$ is odd, then $2^n+1$ is divisible by $3$, since $a^{2k+1} + b^{2k+1}$ is divisible by $a+b$.

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.