GCD, more method

Petrus

Well-known member
Hello,
I wounder if there is more method Then using euclides algoritmen to solve this problem
Simplifie/shorten(I Dont know how to say in english) $$\displaystyle \frac{196707}{250971}$$ and I get GCD=6783 and get the answer $$\displaystyle \frac{29}{37}$$ is there more method? Is there à method that is alot more faster Then this one and that method you take out all prime number?

Last edited:

Staff member

mathbalarka

Well-known member
MHB Math Helper
Ackbach said:
There's a novel way of dividing numbers by others numbers of arbitrary length quickly.
How does division helps to simplify a fraction?

Petrus said:
Is there any method that is alot more faster than this one
I don't see why you think Euclid's method is slow, can elaborate your logic a bit? Well, you might want to look at the Binary GCD algorith then since it shorten the work of finding the GCD quite a bit.

Petrus

Well-known member
How does division helps to simplify a fraction?

I don't see why you think Euclid's method is slow, can elaborate your logic a bit? Well, you might want to look at the Binary GCD algorith then since it shorten the work of finding the GCD quite a bit.
Naa its not really hard, I was just looking for more method to solve it Ackbach

Indicium Physicus
Staff member
How does division helps to simplify a fraction?
Each step of the Euclidean algorithm is a division problem, is it not? If you can speed up each step of Euclid's algorithm, then you speed up Euclid's algorithm.