The Euclidean algorithm is usually presented as a tiny loop. Keep replacing a pair of positive integers by the smaller number and the remainder, and eventually the remainder is zero. That description is correct, but it hides the reason the algorithm works.
Suppose . A number divides both and exactly when it divides both and . So the set of common divisors does not change when we replace by .
This is the whole proof. The pair gets smaller while its greatest common divisor stays fixed. Since non-negative integers cannot decrease forever, the process must stop.
For 252 and 105, the remainders are 42, 21, and then 0. Reading the last non-zero remainder gives
Nothing is guessed; every step preserves precisely the information we care about.
The algorithm is a lovely first example of a recurring mathematical trick: identify an invariant, make progress according to some measure, and let well-ordering finish the argument. The computation is short because the proof has already done the hard work.