Math Behind Euclid’s Theorem

We were taught in our programming classes that, to calculate gcd of two integers efficiently use the Euclid’s algorithm. Magic The Euclid algorithm is programmed as follows: Take a step back and think for a minute. Why does it work? How did you do th...