GCD - The Key Observation

Here is the observation: $\gcd(a, b) = \gcd(b, a \bmod b)$. Why does this work? If $d$ divides both $a$ and $b$, then $d$ also divides $a - b$, and $a - 2b$, and so on. The remainder $a \bmod b$ is just $a$ minus some multiple of $b$.

So any common divisor of $a$ and $b$ is also a common divisor of $b$ and $a \bmod b$. This means you can replace the larger number with a remainder, making the problem smaller each time. The numbers shrink fast.