gen-briefly-explain-the-euclidean-algorithm-and-one-common-misco-0020

Briefly explain the Euclidean algorithm and one common misconception about it.

# The Euclidean Algorithm The Euclidean algorithm finds the **greatest common divisor (GCD)** of two numbers by repeatedly applying this principle: the GCD of two numbers also divides their difference. **How it works:** 1. Divide the larger number by the smaller number 2. Replace the larger number with the smaller number 3. Replace the smaller number with the remainder 4. Repeat until the remainder is 0 5. The last non-zero remainder is the GCD **Example:** GCD(48, 18) - 48 = 18 × 2 + 12 - 18 = 12 × 1 + 6 - 12 = 6 × 2 + 0 - **GCD = 6** ## Common Misconception Many people think the Euclidean algorithm is slow because it involves "repeated division." In reality, it's **remarkably efficient** — the number of steps is at most 5 times the number of digits in the smaller number. Even for very large numbers, it terminates quickly, making it one of the oldest algorithms still in widespread use (in cryptography, computer science, etc.).