# Prove among two integers, at most one is prime.

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

I have no clue :(

-

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.

-

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$

-
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? –  Jorge Fernández 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$.

-