gcd(a, b) = gcd(b, a mod b)

Let $a = bq + r$, where $r = a\bmod b$. We just need to show that $gcd(a, b) = gcd(b, r)$. Let $gcd(a, b) = d$:

$$\begin{align} gcd(a, b) = d & \implies d|ma + nb \quad (m, n \in ℤ)\\& \implies d|a -qb \implies d|r \end{align}$$

This shows that $d$ is a common divisor of $a$, $b$ and $r$. Now let $gcd(b, r) = e$:

$$\begin{align} gcd(b, r) = e & \implies e|sb + tr \quad (s, t \in ℤ)\\& \implies e|qb + r \implies e|a \end{align}$$

This shows that $e$ is also a common divisor of $a$, $b$ and $r$. With this we can conclude two things:

$$\begin{align} & d|b, d|r \implies d\le gcd(b, r) \implies d\le e \\& e|a, e|b \implies e\le gcd(a, b) \implies e\le d \end{align}$$

Which means $d=e$ or $gcd(a,b)=gcd(b, r)$.