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