Number theory fun problem

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???

Solution 1:

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

Solution 2:

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

Solution 3:

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

Solution 4:

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.