Intuition of why $\gcd(a,b) = \gcd(b, a \pmod b)$?

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).$

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$.

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$.

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.

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.