probably the key is “Euclidean theorem”:
gcd(a, b) = gcd(b, a mod b).
i.e., the gcd of two numbers equals the gcd of some smaller numbers.
smtg like gcd(32, 24) equals gcd(24, 8).
the algorithm may be based on this theorem.
so the question is why this holds.