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.

Fractions Help
What do you need help with? Click on one of the following topics...
Adding fractions
Subtracting fractions
Multiplying fractions
Dividing fractions
Subtracting a fraction from a whole number
Multiplying a fraction and a whole number
Dividing a fraction and a whole number
What is a reciprocal?
Changing a fraction to a percentage
Changing a percentage to a fraction
Rounding to a whole number
Finding the lowest common denominator
Reducing a fraction
Euclidean Algorithm
Copyright © 2011 - Mathwizz.com all rights reserved