Euclidean Algorithm

Fractions Help

Home | Fractions menu | Contest

The Euclidean Algorithm is used to find the largest divisor of 2 numbers. Suppose we want the largest divisor of 625 and 7850. We know that 5 divides into both numbers because 625 ends in a 5 and 7850 ends in a 0. Is there a bigger number?

We will call 7850 the big number and 625 the small number. We do 7850 ÷ 625 and find the remainder which is 350. We now make 625 the new big number and 350 the new small number and we keep repeating the steps until the remainder is zero.

Big number Small number Remainder
7850 625 350
625 350 275
350 275 75
275 75 50
75 50 25
50 25 0

We see that the last remainder before 0 is 25. This is the largest number that divides into both 625 and 7850.

privacy policy