Thread: Question regarding using euclidean algorithm to simply fractions in program

In my assignment, I'm asked to be able to take a fraction in as input, and then output it in simplified form if the fraction can be reduced down. Here is the problem i'm facing in my head about this, how do I make sure that the program knows the difference between a fraction that can be simplified, such as : 45/ 210

and a simplified fraction such as 3/4.

I was planning on using a function to find the GDF of the two numbers using modulo and then dividing it by each one to simplify (Euclidean algorithm) , but how can I make it so that the function can distinguish between a simplified fraction and a non-simplified fraction?

Unrelated Hint: use the 'Extended Euclid's Algorithm' and you can skip the division.

This is a math problem actually. If the numerator and denominator are mutually prime (coprime) then it is already in it's simplest form. The best algorithm to figure out if they are mutually prime is the Euclidean algorithm you are already familiar with. It computes the greatest common divisor, which would be one if they are mutually prime. It should be easy enough to code via a loop or a recursive function that algorithm.

Thus if gcd(a,b)=1 , the fraction can not be reduced since there is no common factor other than 1. It's that simple. You can write a function to compute that.