The Euclidean algorithm is an efficient method for computing the greatest common divisor (GCD) of two integers. It is based on the principle that the GCD of two numbers does not change if the larger number is replaced by its difference with the smaller number.

How it works:

1. Start with two numbers a and b (where a ≥ b)
2. Divide a by b to get quotient q and remainder r
3. Write: a = b × q + r
4. Replace a with b and b with r
5. Repeat until the remainder is 0
6. The last non-zero remainder is the GCD

Example: GCD(48, 18)
48 = 18 × 2 + 12
18 = 12 × 1 + 6
12 = 6 × 2 + 0
Therefore, GCD(48, 18) = 6