Exercise 1.2.47* ($2^a +1$ is not divisible by $2^b - 1$)

Proof. Reasoning by contradiction, assume that there are positive integers $a,b$, with $b>2$, such that

The Euclidean division gives $a=\mathit{bq}+r$, where $0\le r<b$. Reducing modulo $2^b-1$, using $2^b\equiv 1(\mathit{mod}{2}^b-1)$, we obtain

Since $2^a+1\equiv 0(\mathit{mod}{2}^b-1)$, this gives $2^r+1\equiv 0(\mathit{mod}{2}^b-1)$, that is

Since $2^b-1\mid 2^r+1\ne 0$, $2^b-1\le 2^r+1$.

If $2^b-1=2^r+1$, then $2^b=2^r+2$. Here $b>2$, thus $2^r=2^b-2$ is even, so $r\ge 1$. The division by $2$ gives $2^{r-1}=2^{b-1}-1$. Since $b>2$, $2^{r-1}=2^{b-1}-1$ is odd, thus $r=1$. Then $2^b-1=3$, so $b=2$: this contradicts the hypothesis $b>2$. This proves that $2^b-1\le 2^r$.

If $2^b-1=2^r$, with $b>2$, then $2^r$ is odd, so $r=0$ and $2^b=3$ : this is impossible. Therefore $2^b-1\le 2^r-1$, so $2^b\le 2^r$. Hence $b\le r$.

But $r$ is the remainder of the division $a=\mathit{bq}+r$, so $r<b$. This is a contradiction.

Conclusion: If $a,b$ are positive integers, with $b>2$, then $2^a+1$ is not divisible by $2^b-1$. □