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 Divisions

GCD (72, 16) = 8

  • Top