Take the 2-minute tour ×
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.

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


I have no clue :(

share|improve this question
add comment

3 Answers 3

up vote 32 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|improve this answer
add comment

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|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
2  
isnt this solution too complicated? –  Bananarama Dec 20 '12 at 19:15
    
@Khromonkey, have you seen the generalization? –  lab bhattacharjee Dec 23 '12 at 3:54
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.