5
$\begingroup$

Not sure what approach to take with this:

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

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

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – lab bhattacharjee May 26 '13 at 10:59
0
$\begingroup$

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

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