For $a,b>2$, $a,b\in \Bbb{N}$ , prove that $2^a+1$ is never divisible by $2^b-1$

Question

I have to prove that for $a,b>2$, $a,b\in \Bbb{N}$ that $2^a+1$ is never divisible by $2^b-1$. The method I used is by taking cases, first of them being $b>a$. Now since $b>a$ implies $2^b-1>2^a+1$. That would mean that $2^a+1$ is never divisible by $2^b-1$.

For the case $a=b=k$, I wrote $2^k=2n$. So the questions reduces down to the fact that $2n+1$ is not divisble by $2n-1$. Now if you look at the sequence formed by $2n+1$ and $2n-1$ for different values of $n$ it is a sequence of odd numbers(i.e $1,3,5,\cdots$).Now given any value of $n$ the number $2n+1$ gives a number in the sequence whose preceding number is given by $2n-1$. Now given two consecutive odd numbers(By consecutive I mean in this arithmetic progression $(1,3,5,\cdots$)) there gcd is always one and hence not divisible.

But I do not know how to do it for the case $a>b$

Answer 1

Suppose $a = bq + r$, where $0 \leq r < b, q \geq 1$.

Assume: $2^a+1 = k(2^b-1) \Leftrightarrow k+1 = k2^b-2^a = 2^b(k-2^{a-b})$.

Thus, $k$ is odd, say $k = 2k_1-1$, so $2k_1 = 2^b(2k_1-1-2^{a-b})$. This implies $k_1 =2^{b-1}k_2$. So $k_2 = 2^bk_2-1-2^{a-b}$, or $1+2^{a-b} = k_2(2^b-1)$.

Continue this procedure $q$ times, we obtain: $1+2^r=k_q(2^b-1)$. This equation has no positive integer solution as you proved at the beginning.

Answer 2

Let $a=qb+r$ with Euclidian division, $0 \le r< b$, then $$2^a+1 \equiv 2^{qb+r}+1\equiv 2^r+1 \mod 2^b-1.$$

So it can't be congruent to zero.

(Moreover, For $b=2$, $a=r=1$ satisfies. The reason is the fact of $3$: $\;\;$ $3=2^2-1=2+1$).

Answer 3

The ideia is reduce to your first case. Divide $a$ for $b$ and write $a = bq + r$, where $0 \le r < b$. Now you see that

$2^a + 1 = 2^{bq+ r} + 1 = 2^r\cdot (2^b)^q + 1$

Use Newton binom and write

$(2^b)^q = \sum_{j=0}^{q} \binom{q}{j} (2^b - 1)^j$

Hence, you have:

$2^a + 1 = 2^r\{ \sum_{j=0}^{q} \binom{q}{j} (2^b - 1)^j\} + 1$

Now, for $j > 0$, $\binom{q}{j} (2^b - 1)^j$ is divisible by $2^b - 1$. The remainder term is $2^r + 1$ which is not divisible by $2^b - 1$, since $r < b$.