Euclid’s Algorithm

This program implements Euclid’s Algorithm to reduce a given fraction to lowest terms. This is done by finding the greatest common divisor (GCD) of the numerator and denominator. The GCD of two integers is the largest integer which divides them both. A fraction is reduced to lowest terms by repeatedly dividing both the numerator and the denominator by their GCD. Euclid’s Algorithm finds the GCD to two integers, say u and v by finding the GCD of u – v and v (if u > v).

Tweet