Can fractions be simplified without guessing and checking?

[Spiralshell]

So, I was thinking about how we would simplify say 2/4 -> 1/2. But without any memorization and guessing and checking how do we know if a fraction can be simplified? I was looking all over the internet and I can't seem to find anything.

I am especially curious when it comes to a large fraction say 99809 / 99907. I am not a math whiz or anything... I was just curious how we can mathematically determine whether or not a fraction can be simplified. That is without any electronic means...

 

[sjb-2812]

Well, for instance, for 99809 / 99907 you might try things like highest common factor sieves?

 

[Hertz]

Hmm, I may be in over my head, but I'll chime in anyways.

If you want to find a general, arbitrary way to determine if a fraction can be simplified, you (may) first need to determine a general way to find the factors of ANY number. A fraction simplifies when the numerator and denominator have a similar factor. So if you could, in general, reduce the numerator and denominator into products of factors, these similar factors would cancel out. I'm not entirely sure if this is possible or how you would go about doing it though.

 

[Matterwave]

Factorizing large numbers is, in fact, a difficult problem. We use this fact to encrypt, for example, credit card numbers. If you could do it in a short amount of time, our credit card systems would be much less secure.

But if you're looking at maybe just 3-5 digit numbers, there should be some algorithms out there that won't take too long. If you're looking at a 20+ digit numbers, then probably not.

 

[Spiralshell]

Thanks for the responses.

@Matterwave I had no idea and that would explain why I can't find anything about it.

 

[gopher_p]

Euclid's Algorithm (https://en.wikipedia.org/wiki/Euclidean_algorithm) can be used to find the greatest common divisor of the numerator and denominator to reduce the fraction to "simplest" terms.

 

[lurflurf]

^Yes is a good choice for simplicity

another choice is
http://en.wikipedia.org/wiki/Binary_GCD_algorithm
and for large numbers
http://en.wikipedia.org/wiki/Lehmer's_GCD_algorithm

 

[SteamKing]

If you google "fraction simplification", you get about 4.8 million hits.

Fractions can be simplified only if the numerator and the denominator share common multiplicative factors.

For example, the utterly trivial \frac{2}{4} = \frac{2}{2\times2} = \frac{1}{2}

where the 2 in the numerator cancels with one of the 2s in the denominator