Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Not sure what approach to take with this:

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

share|improve this question
13  
One of them must be divisible by 3. –  ՃՃՃ May 26 '13 at 5:35

5 Answers 5

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

share|improve this answer

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

share|improve this answer
2  
(+1) Very neat! –  TMM May 26 '13 at 13:06

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

share|improve this answer
3  
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

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.