I don't know if this is the fastest method of proving it, but:

A way to prove it is by considering the Extended Euclidean Algorithm, which

gives a decreasing sequence of positive integers g_k:

g_k=m_k*a+n_k*b

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

RonL