# Euclidean Algorithm

**Euclid's algorithm** is a procedure for calculating the **greatest common divisor (GCD)** of any two numbers. The steps are:

1. Divide the largest number by the smallest.

2. If:

1. The division is exact, the divisor is the** GCD. **

2. The division is not exact, divide the divisor by the remainder obtained and continue in this process to obtain an exact division. The last divisor is the** GCD.**

GCD (72, 16)

GCD (72, 16) = 8

Subject

Site