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.
 A: Hint: Show that more generally $\gcd(a,b)=\gcd(b,a-bk)$ for any integer $k$.
Then note that $a\pmod b = a-bk$ for some $k$.
A: Let $\, a\ {\rm mod}\ b = a-kb.\, $ If $\, d\mid b\ $ then $\ d\mid \color{#0a0}{a-kb}\iff d\mid \color{#c00}a.\ $ Thus $\ \color{#0a0}{a-kb},b\ $ and $\ \color{#c00}a,b\ $ have same set $S$ of common divisors $\,d,\,$ so they have the same greatest common divisor $\,(= \max S).$
A: The crux of all proofs is that $gcd(b,a) = gcd(b,a-b)$.
This should be easy to see intuitively; if you add or subtract two multiples of $g$ you get a multiple of $g$, so all factors are retained both ways.
Once you have that, you know that you can subtract one number from the other as many times as you like, without changing the gcd.
If you continue subtracting $b$ from the second number, you will eventually arrive at a number between 0 and $b-1$; specifically $a\bmod b$.
A: For me it all really comes down to this equation
$$
a=qb+r
$$
For if $d$ divides $b$ and any of the two $a$ or $r$ it has to divide the last of $a$ and $r$ too in order for this equation to hold.
A: 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.
