6
$\begingroup$

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


I have no clue :(

$\endgroup$
33
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Thomas Andrews Dec 20 '12 at 18:51
  • 2
    $\begingroup$ isnt this solution too complicated? $\endgroup$ – Jorge Fernández Hidalgo Dec 20 '12 at 19:15
  • $\begingroup$ @Khromonkey, have you seen the generalization? $\endgroup$ – lab bhattacharjee Dec 23 '12 at 3:54
4
$\begingroup$

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

$\endgroup$

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.