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

1. Jun 21, 2012

### samkolb

1. The problem statement, all variables and given/known data
If a, b are positive integers, b > 2, prove that

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

2. Relevant equations
prime factorization of integers

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

2. Jun 22, 2012

### Joffan

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