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
7850625350
625350275
35027575
2757550
755025
50250

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