Euclidean Algorithm

Fraction Unit

Math 300

Dr. Wilson







we can probably see that the greatest common factor for both the top and bottom is 3, and that by dividing the top and bottom by 3, our fraction will reduce to 8/35.


We need is to find the GCF(24,105). If we had that we could not only do the problem listed above, but also



While the numbers are quite different, the process of reduction will be equivalent. However, since the second number is an improper fraction, we can change it to a mixed number.






So 24/105 simplifies if and only if 9/24 simplifies. By the same reasoning, 9/24 simplifies if and only if 24/9 simplifies. But






The original fraction reduces if and only if 6/9 reduces. Thus GCF(24, 105) = GCF(6, 9). Again, 6/9 reduces if and only if




reduces. The conversion looks like



Of course, 3/6 reduces because 3 goes into 6



So 3 = GCF(3,6) = GCF(6,9) = GCF(9,24) = GCF(24,105). One can obtain this result by simply doing the series of division problems,





and that process is known as the Euclidean Algorithm. Keep dividing the remainder into the divisor until you get a problem that comes out even. The divisor in the problem that comes out even which is the last non zero divisor is the greatest common factor.


next page

Euclidean Algorithm