2^a + 1 not divisible by 2^b - 1

[samkolb]

Homework Statement

If a, b are positive integers, b > 2, prove that

2^a + 1 is not divisible by 2^b - 1.

Homework Equations

prime factorization of integers

The Attempt at a Solution

Suppose (2^a + 1)/(2^b - 1) = x, x an integer.

Then x + 1 = (2^a + 2^b)/(2^b - 1).

Write x + 1 = m2^r, m odd, r non-negative. Then

(2^b - 1)m2^r = 2^a + 2^b.

Let k = min{a,b,r}. Then

(1) (2^b - 1)m2^(r - k) = 2^(a - k) + 2^(b - k)

For most choices of k, (1) leads to contradiction. For example, if k = r, r < a, r < b, then LHS of (1) is odd while the RHS is even. The tricky cases are k = r = a with a < b, and k = r = b with b < a. In both these cases both LHS and RHS of (1) are odd.

 

[Joffan]

Hmm. Try looking at the values of $(2^a+1)$ mod $(2^b-1)$ as $a$ increases. Starting with $a=b$.