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.

Say $a,b > 2 $ are integers. Then we have that $2^a + 1$ is not divisible by $2^b - 1$.

Any thoughts on how to tackle this problem???

share|improve this question

4 Answers 4

up vote 7 down vote accepted

I think that this is the same idea as CL, but slightly different approach.

Let $a=qb+r \,;\, 0 \leq r <b$.

Using $2^b\equiv 1 \pmod {2^b-1}$ we get

$$2^a+1 \equiv (2^b)^q2^r+1 \equiv 2^r+1 \pmod {2^b-1}$$

It is easy to prove that for $b>2$ we have

$$2^{b-1}+2 <2^b$$

but this implies that

$$1 \leq 2^r+1 < 2^b-1$$

which shows that

$$ 2^a+1 \neq 0 \pmod {2^b-1}$$


P.S. Random observation: I think the proof is the same if we replace $2$ by any positive integer $k\geq 2$. Thus, if $k \geq 2$ is positive integer, and $a,b >2$ then $k^a+1$ is not divisible by $k^b-1$.

share|improve this answer

Let $a = bq + r$ where $0 \leq r < b$. Hence, $$2^a+1 = 2^{bq} \cdot 2^r +1 = (2^{bq}-1)\cdot 2^r + 2^r+1$$ But $2^b-1$ divides $2^{bq}-1$ since $(x-1)$ divides $x^m-1$ for all $m \in \mathbb{N}$.

Hence, if $2^b-1$ divides $2^a+1$, then $2^b-1$ has to divide $2^r+1$. But $0 \leq r < b$. Hence, we need $$2^b-1 \leq 2^r + 1 \leq 2^{b-1} + 1$$ i.e. $$2^b - 2^{b-1} \leq 2$$ This is possible only if $b=1$ or $2$. But we are given that $b > 2$.

share|improve this answer

Hint: If $a>b$,

$$2^a + 1 = (2^{a} - 2^{a-b}) + (2^{a-b} +1).$$

The condition that $a, b >2$ comes when you're studying the base case.

$$2^2 - 1 = 2^1 + 1$$

share|improve this answer
    
We also have that $2^3+1 = 9$ is divisible by $2^2-1 = 3$... –  PseudoNeo Feb 6 '13 at 23:54
    
@PseudoNeo But in that case, $a>b$, so you're not studying the base case. –  Calvin Lin Feb 6 '13 at 23:55

Hint $\ $ Notice that $\rm\ a \equiv c\pmod{b}\:\Rightarrow\:x^a\equiv x^{c}\pmod{x^b\!-1}\ $ since

$$\rm mod\ x^b\!-1\!:\,\ \color{#C00}{x^b\equiv 1}\:\Rightarrow\:x^a = x^{c+bn} = x^{c} (\color{#C00}{x^b})^n\equiv x^{c} \color{#C00}1^n\equiv x^{c}\quad\ \ $$

Hence for $\rm\,x = 2\,$ and $\rm\: 0 \le c < b,\:$ i.e. $\rm\ c = (a\ mod\ b),\:$ we deduce that

$$\rm mod\ 2^b\!-1\!:\,\ 2^a\! + 1 \equiv 2^{c}\! + 1 < 2^b\!-1\ \ by\ \ \,c< b\ \ and\ hypotheses.$$

Thus we have $\rm\ mod\ 2^b\!-1\!:\,\ 2^a\!+1\not\equiv 0,\ $ hence $\rm\, 2^b\!-1\nmid 2^a\!+1.$

Remark $\ $ For a more general perspective see here on divisibility sequences.

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.