For a > b, GCD(a, b) = GCD(b, r = a%b). You can use the Division Theorem to prove the equation holds.