Prove $2^b-1$ does not divide $2^a + 1$ for $a,b>2$

Hint

Now, let $a=qb+r$ with $0 \leq r <b$. Then

$$2^a+1=2^a-2^r+2^r+1 $$

Show that $2^b-1 | 2^a-2^r$ and conclude that $2^b-1|2^r+1$. Now prove that this contradicts $0 \leq r <b$.

Do you know the theorem:

$$\gcd(a^n-1,a^m-1)=a^{\gcd(m,n)}-1?$$ If so, use it by noting that if $2^b-1\mid 2^a+1$ then $2^b-1\mid 2^{2a}-1$, so $b\mid 2a$. Now consider cases where $b\mid a$ or $b=2b_0$ with $b_0\mid a$.

Here’s a very elementary approach that leads naturally to a proof. The numbers $2^a+1$ and $2^b-1$ have very simple forms in binary:

$$2^a+1=1\underbrace{0000\ldots 0000}_{a-1\text{ zeroes}}1\;,$$

and

$$2^b-1=\underbrace{1111\ldots 1111}_{b\text{ ones}}\;.$$

Assume that $a>b$, as otherwise it’s clear that $2^b-1\nmid 2^a+1$, and imagine doing a standard long division. The first $1$ in the quotient will go over the $b$-th zero in $2^a+1$, and you’ll subtract

$$\underbrace{1111\ldots 1111}_{b\text{ ones}}\underbrace{000\ldots 000}_{a-b\text{ zeroes}}$$

from $2^a+1$ to leave

$$1\underbrace{0000\ldots 0000}_{a-b-1\text{ zeroes}}1\;.\tag{1}$$

The number in $(1)$ has the same form as $2^a+1$; in fact it’s $2^{a-b}+1$. You’ve reduced the original problem to another of the same kind but with a smaller exponent in the dividend. Since this exponent must be a non-negative integer, you have the guts of a proof by induction on that exponent: if you already knew that $2^b-a\nmid 2^{a-b}+1$, you’d be done, and if you were doing a proof by induction, that would be part of your induction hypothesis.

In this case it’s simplest to phrase the induction in terms of a minimal counterexample: if there is any $n$ such that $2^b-1\mid 2^n+1$, let $a$ be the least such $n$. Clearly $a>b$. Now convert the calculations above to a more algebraic form:

$$2^a+1=\left(2^b-1\right)\cdot 2^{a-b}+\left(2^{a-b}+1\right)\;,$$

so

$$2^{a-b}+1=\left(2^a+1\right)-\left(2^b-1\right)\cdot 2^{a-b}\;.\tag{2}$$

$2^b-1$ divides the righthand side of $(2)$, so $2^b-1\mid 2^{a-b}+1$. But $a-b<a$, contradicting the minimality of $a$, so in fact there is no $n$ such that $2^b-1\mid 2^n+1$.

This is of course exactly the proof suggested in some of the other answers; I’m merely pointing out one way in which you might fairly naturally discover it.

Note that the binary notation merely makes it especially easy to see what’s happening, at least if you’ve used it enough to have some feel for it. Even without it you might reasonably just try to divide $2^a+1$ by $2^b-1$. Since $2^a=2^b\cdot2^{a-b}$, it’s clear that the quotient is greater than $2^{a-b}$, you could try that as a first approximation, subtracting $(2^b-1)\cdot 2^{a-b}$ from $2^a+1$ to see what remainder is left:

$$2^a+1-\left(2^b-1\right)\cdot 2^{a-b}=2^{a-b}+1\;,$$

and again you’d discover that you’ve reduced the problem to a smaller one of the same kind.

Assume otherwise and let $a$ be the nonnegative integer such that $2^b-1\mid 2^a+1$ for some $b>2$. If $2^a+1=k(2^b-1)$ with $k\ge 1$, then $$2^{a-b}+1 = 2^a+1-2^{a-b}(2^b-1)=(k-2^{a-b})(2^b-1).$$ If $a\ge b$, this shows that $2^b-1\mid 2^{a-b}+1$, contradicting minimality of $a$. Therefore $a\le b-1$. But then we have $$2^b-1=2^{b-1}+2^{b-1}-1\ge 2^{b-1}+3>2^a+1$$ contradicting $2^b-1\mid 2^a+1$.

Note that $b=2$ allows us to find $2^2-1=3\mid 9=2^3+1$ or $33=2^5+1$ and so on.

Hint. We have $b\lt a$. Let $a$ be the smallest integer for which the criterion is satisfied. Now consider $2^a+1+2^b-1=2^b(2^{a-b}+1)$ which is divisible by $2^b-1$. Argue by contradiction.