Euclidean Gcd Algorithm

Write a function gcd(a, b) that finds the Greatest Common Divisor — the largest positive integer that divides both a and b without a remainder. For example, gcd(48, 18) = 6. You must use the Euclidean Algorithm, not a brute-force loop.

The Euclidean Algorithm is based on a mathematical property: gcd(a, b) = gcd(b, a % b). By repeatedly replacing the larger number with the remainder of dividing the two, the pair eventually reduces to (gcd, 0). This is dramatically faster than checking every number from 1 to min(a, b).

1. While b is not 0, replace (a, b) with (b, a % b). 2. When b becomes 0, a holds the GCD. 3. The order of a and b doesn't matter — the algorithm self-corrects after one iteration.

- Using a brute-force loop from min(a, b) down to 1, which is O(N) and too slow for large inputs - Getting the swap wrong: it must be a, b = b, a % b (not a % b, b) - Not handling the case where one input is 0: gcd(0, n) = n and gcd(n, 0) = n - Confusing GCD with LCM (Least Common Multiple): LCM(a, b) = (a * b) / GCD(a, b)

The Euclidean Algorithm is over 2,300 years old and is one of the most elegant algorithms in computer science. Its logarithmic time complexity makes it practical even for numbers with hundreds of digits. This is a foundational algorithm used in cryptography (RSA), fraction simplification, and many number theory problems.