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 \\ & \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 \\ & \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)\).