Divide the larger number by the smaller and keep only the remainder. The pair (smaller number, remainder) has the same GCD, so repeat until the remainder is : the last nonzero remainder is the GCD.
| Step | On | |
|---|---|---|
| 1 | Divide the larger number by the smaller. Write the division as dividend divisor quotient remainder, with the remainder between and the divisor (how to compute a remainder). | |
| 2 | Replace the pair by (divisor, remainder). Any number that divides both and also divides , so the GCD does not change. | |
| 3 | Repeat until the remainder is 0. Each remainder is smaller than the last divisor, so the numbers shrink and the process stops. | , |
| 4 | Read the last nonzero remainder. It is the divisor in the final division, the one that leaves remainder . |