# Proving that either $2^n-1$ or $2^n+1$ is not prime

Not sure what approach to take with this:

Prove that at least $2^n-1$ or $2^n+1$ is composite $\forall$ $n>2$

• One of them must be divisible by 3. – ՃՃՃ May 26 '13 at 5:35
• This answer proves nicely what you are asking for. – Physicist137 Dec 3 '16 at 18:18

Consider $2^n -1 , 2^n$ and $2^n+1$ we know one of them is multiple of 3 as far as $2^n$ cant be divided by 3 so one of $2^n-1$ or $2^n+1$ must divided by 3.

EDIT : for $n =1$ we have this sequence : $1,2,3$ and for $n=2$ we have this sequence : $3,4,5$. as you see we have a number in both series that divided by 3 but because this number is 3 and 3 is prime we must consider $n>2$.

$$(4-1)|4^n-1=(2^n-1)(2^n+1)$$ so $3|(2^n-1)$ or $3|(2^n+1)$ since $3$ is prime. Also $(2^n+1)>(2^n-1)>3$.

Hint: $\ 3\nmid a,\ \,3\mid (a\!-\!1)a(a\!+\!1)\!\stackrel{\color{#0a0}{\rm Remark}}{\Rightarrow} 3\mid a\!-\!1\ \ {\rm or}\ \ a\!+\!1,\,$ so $\,a>4\Rightarrow a\!-\!1\ \ {\rm or}\ \ a\!+\!1\,$ not prime.

$\color{#0a0}{\rm Remark\!:}\,$ More generally, any sequence of $\,n\,$ consecutive naturals has an element divisible by $\,n.\,$ This has a simple inductive proof:  shifting such a sequence by one does not change its set of remainders mod $\,n,\,$ since it replaces the old least element $\:\color{#C00}a\:$ by the new greatest element $\:\color{#C00}{a+n}$ $$\begin{array}{}& \color{#C00}a, &\!\!\!\! a+1, &\!\!\!\! a+2, &\!\!\!\! \cdots, &\!\!\!\! a+n-1 & \\ \to & &\!\!\!\! a+1,&\!\!\!\! a+2, &\!\!\!\! \cdots, &\!\!\!\! a+n-1, &\!\!\!\! \color{#C00}{a+n} \end{array}\qquad$$

Since $\: \color{#C00}{a\,\equiv\, a\!+\!n}\pmod n,\:$ the shift does not change the remainders in the sequence. Thus the remainders are the same as the base case $\ 0,1,2,\ldots,n-1\ =\:$ all  possible remainders  mod $\,n.\,$ Therefore the sequence has an element with remainder $\,0,\,$ i.e. an element divisible by $\,n.$

• Why are you not using \rm for variables today? – Parth Kohli May 26 '13 at 14:57

As $n>2,2^n-1>3$

If $n$ is even, $=2m$(say), $2^n-1=2^{2m}-1=4^m-1$ which is divisible by $4-1=3$ as $(a-b)$ divides $a^n-b^n$ for integer $n\ge 0$

If $n$ is odd, $=2m+1$(say), $2^{2m+1}+1=2^{2m+1}+1^{2m+1}$ which is divisible by $2+1=3$ as $(a+b)$ divides $a^{2m+1}+b^{2m+1}$ for integer $m\ge 0$

Alternatively,

$(2^n-1)(2^n+1)=4^n-1$ is divisible by $4-1=3,$

but $2^n+1>2^n-1>3$

References : Fermat Prime 1,2, Mersenne Prime1,2

• The necessary condition of $2^n-1$ to be prime is that $n$ is prime and the necessary condition of $2^n+1$ to be prime is that $n$ must be of the form $2^m$ where integer $m\ge0$ So, we need $2^m$ to be prime $\implies m=1$ For $m=1,2^m=2\implies 2^{2^1}-1=3$ and $2^{2^1}+1=5$ – lab bhattacharjee May 26 '13 at 10:59

If n is composit, so is $2^n -1$. If n is prime or has an odd factor, $2^n +1$ is composit.