A way to prove it is by considering the Extended Euclidean Algorithm, which
gives a decreasing sequence of positive integers g_k:
(with m_k and n_k integers) each of which is divisible by the gcd(a,b), and
if g_k>g another step can always be performed, so the sequence eventualy
reaches a k such that g_k=g.
A not very clear explanation of the EEA can be found here.