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

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$

• Commented Apr 26, 2016 at 15:07

Let $$a=qb+r$$ with Euclidean 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$$).

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.

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