Intuition of why $\gcd(a,b) = \gcd(b, a \pmod b)$? Does anyone have a intuition or argument or sketch proof of why $\gcd(a,b) = \gcd(b, a \pmod b)$?
I do have a proof and I understand it, so an intuition would be more helpful.

The proof that I already have:
I show $\gcd(a,b) \mid \gcd(b, a \pmod b)$ and $\gcd(b, a \pmod b) \mid \gcd(a, b)$ which implies $\gcd(a,b) = \gcd(b, a \pmod b)$ and stuff is non-negative.
WLOG $a \geq b$
$\gcd(a,b) \mid a$
$\gcd(a,b) \mid b$
so it divides any linear combination of a and b
Since $a \pmod b = a - qb$ then:
$\gcd(b, a - qb) = bx + (a-qb)y$
$\gcd(b, a - qb) = bx + ay - qby $
$\gcd(b, a \pmod b) = b(x-qy) + ay$
which is a LC of $a$ and $b$.
So $\gcd(a,b) \mid \gcd(b, a \pmod b)$.
Other direction is nearly identical.

Suppose each of $a$ and $b$ is an integer number of miles.  Then so is $a\bmod b$.
If a mile is a "common measure" (as Euclid's translators say) of both distances, then a mile is a common measure of what's left when $b$ has been taken from $a$ as many times as possible.
