This is the way I prove $(b, m) = (b + mx, m)$:
Suppose $(b, m) = t$.
Then $b = pt$, $m = qt$, where $(p, q) = 1$.
$b + mx = pt + qtx$.
So $(b + mx, m) = (pt + qtx, qt) = t = (b, m)$
But if I am given $(b,m)$, I can't come up with $(b, m) = (b + mx, m)$ right away.
I need some better explanation about the relation between $(b, m)$ and $(b + mx, m)$.
On
Key idea: we can replace a gcd argument with one that yields the same set of common divisors.
Note if $\,d\mid m\,$ then $\,d\mid b\iff d\mid b\!+\!mx.\,$ Thus $\,m,b\,$ and $\,m,\,b\!+\!mx\,$ have the same set $S$ of common divisors $\,d,\,$ so they have the same greatest common divisor $(= \max S)$.
Using modular alrithmetic we can express this equationally, enabling a geometrical view:
${\rm mod\ d}\!:\ $ if $\, m\equiv 0\,$ then $\ b\equiv 0\iff b+mx\equiv 0,\,$ i.e. the systems $\,m\equiv 0,b\equiv 0\,$ and $\,m\equiv 0,\, b+mx\equiv 0\,$ are equivalent.
Geometrically, if we rename to customary variables, then the equivalent systems of equations is $\ x\equiv 0, y\equiv 0\iff x\equiv 0,\, y+mx\equiv 0.\,$ This says the the origin $\, (x,y) \equiv (0,0)\,$ can be specified either as the intersection of the $y$ axis $(x\equiv 0)$ with the $x$ axis $(y\equiv 0)$ or, equivalently, as the intersection of the $y$ axis $(x\equiv 0)$ with the line $\, y\equiv -mx.\,$
If you know linear algebra you will recognize this equivalence as the effect of an elementary linear transformation. This connection between linear algebra and number theory will be made more explicit when one studies module theory in abstract algebra.
If $x$ is an integer, then $(b,m) = (b+mx,m)$.
If $c = (b,m)$ you can easily show that $c\mid (b+mx)$ and $c\mid m$. So $c$ is a common divisor of both $b+mx$ and $m$. Thus $(b,m) \leq (b+mx,m)$ (by definition of $\gcd$).
On the other hand if $d = (b+mx,m)$, then first note $d\mid m$. Then $d\mid b$ as well, since $d\mid (b+mx)$ and $d\mid mx$. So $(b+mx,m) \leq (b,m)$.
Combining both inequalities yields $(b,m) = (b+mx,m)$.