On the proof of $2^b-1$ does not divide $2^a+1$. 
Proposition. For any integer $a$ and $b$ where $b>2$, we never have $2^b-1|2^a+1$.

WLOG let $b<a$. The proof uses a critical fact that can be stated very simply as follows:

$2^a+1$ leaves a reminder of the form $2^r+1$ when divided by $2^b-1$, where $r\leq b$.

This again, directly follows by the following equation:

$$2^{r+kb}+1=2^r(2^{kb}-1)+(2^r+1).$$

I am digging some insight from these steps so that the above step is not just a “trick” to use. For example in the proposition the base $2$ can be replaced by any positive integer $x\geq 2$. And observe that the exponential function minus $1$(it is not true in general for $x^n+k$ where $k\neq -1$) satisfies the following functional equation:

One of the solution set for $f(x+y)=f(x)f(y)+f(x)+f(y)$ where $f:\mathbb Z_+\to \mathbb Z$ is the set of all exponential function minus $1$: $f(x)=x^n-1$, where the integer $x>1$ and $n>1$.

I am looking for a way to make the solution of the first line proposition not a “trick” to memorize, but a link to a theory or a more general result so the proof will follow naturally.

Claim:  If $a,b,r, n\in \mathbb N$ if $a \equiv r \pmod b$ then $n^a \equiv n^r\pmod{n^b -1}$.
Pf:  wolog $r < a$ so there is a $k > 0; k\in \mathbb N$ so that $a= kb + r$.
So $n^a = n^{a-b}(n^b-1)+ n^{a-b}\equiv n^{a-b}\pmod{n^b-1}$.
and by induction, for any $a-kb \ge b$
$n^a \equiv n^{a-(k-1)b} = n^{a-kb}(n^b-1) + n^{a-kb}\equiv n^{a-kb}\pmod{n^b - 1}$.
And so $n^a\equiv n^{n-kb}=n^r\pmod {2^b -1}$
.....
And that's all.  Just because something is "tricky" doesn't mean it isn't valid.
==== old answer =====
$2^a + 1 \equiv m \pmod {2^b -1}$ means there is a $k$ so that $2^a+1 =k*(2^b-1) + m$. 
To find so possible values for $k, m$ (and if $0 \le m < 2^a + 1$ then then $k$ and $m$ are unique) we notice.
$k*(2^b-1) + m = 2^k-k + m$.
If $k = 2^{a-b}$ we get $2^{a} + 1 = 2^{a-b}(2^b -1) + m = 2^a - 2^{a-b} + m$ and so
$2^{a-b} + 1 = m$ and 
That's that.  I'm not sure why that seems like "trick".
Or we couls simply note:
$2^a + 1 = 2^{b-a}2^b + 1 = 2^{b-1}(2^b - 1) + 2^{b-a} + 1\equiv 2^{b-a} +1\pmod{2^b -1}$.

or example in the proposition the base 2 can be replaced by any positive integer x≥2.

Sure.
If $b < a$ then
$x^a+1 = x^{a-b}(x^{b}-1) + x^{a-b} + 1 \equiv x^{a-b} + 1\pmod {x^b-1}$.
We can make that a theorem (never "theory".... math doesn't have "theories").

Theorem:  for $a, b \in \mathbb N$  then for any $k\in \mathbb Z$ so that $a + kb \ge 0$ then $n^{a}\equiv n^{a+kb}\pmod {n^b -1}$.

Pf:  If $a > b$ then $n^a = n^{a-b}(n^b -1) + n^{a-b}\equiv n^{a-b}\pmod {n^b-1}$ and by induction $n^a \equiv n^{a-kb}\pmod {n^b-1}$ for all $k; a-kb \ge 0$.  And $n^{a+kb} \equiv n^{a}\pmod{n^b -1}$ for all $k \ge 0$ by induction.
