Euclidean Algorithm

Fraction Unit

Math 300

Dr. Wilson

Example:

 

 

Reduce

 

 

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.

 

 

because

 

 

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

 

 

because

 

 

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.

top

next page

Euclidean Algorithm