6
$\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$
2
  • 13
    $\begingroup$ One of them must be divisible by 3. $\endgroup$
    – ՃՃՃ
    May 26, 2013 at 5:35
  • $\begingroup$ This answer proves nicely what you are asking for. $\endgroup$ Dec 3, 2016 at 18:18

5 Answers 5

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$
0
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$
1
  • 3
    $\begingroup$ Why are you not using \rm for variables today? $\endgroup$
    – P.K.
    May 26, 2013 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$
1
  • $\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$ May 26, 2013 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .