Euclidean Algorithm (GCD)

Euclid, ~300 BC

Described in Euclid's Elements around 300 BC, this algorithm finds the greatest common divisor of two integers by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller. The visualization shows two horizontal bars representing a and b, shrinking with each modular reduction step until the GCD is found.