Simplifying Fractions Involving Large Numbers

Question

I am doing a lesson on simplifying fractions and the lesson said to find the GCD (Greatest Common Divisor). If the fraction is large, factoring both the top and bottom numbers would be very time consuming. So what is the easiest/simplest way of factoring large numbers? Ex: $$\frac{5,692}{84}$$

You could just go and check all numbers for divisibility but with large numbers that takes a long time. You could also use factoring tree but that does not always catch all of the factors and takes up a lot of space. What is the quickest way of factoring these types of numbers? Or is their a easier way of simplifying fractions than finding the GCD ?

Answer 1

For any integers $A,B,C$ we have $\gcd (A,B)=\gcd (A,B-AC).$

So $$\gcd (84, 5692)=\gcd (84,\;5692-84\cdot 70)=$$ $$=\gcd (84,-188)=\gcd(84,188)=$$ $$= \gcd (84,\;188-84\cdot 2)=\gcd(84,20)=$$ $$=\gcd(84-20\cdot 4,20)=\gcd (4,20)=$$ $$=\gcd (4,20-4\cdot 5)=\gcd (4,0)=4.$$

....In the first displayed line above we could begin with "$67$" instead of "$70$" because $5692=84\cdot 67 +R$ where the remainder $R$ is between $0$ and $84$. But when working manually, it is often easier to employ a "rounder " number like $70$. And once you get to small values like $\gcd (84,20)$ or $\gcd (4,20)$ it can be calculated at a glance.

So $5692/84=(5692/4)/(84/4)=1423/21$ in lowest terms

Answer 2

One way is to divide the numerator and denominators by common factors (you do not need to compute the GCD explicitly). For example, $$\frac{5692}{84} = \frac{2\times2846}{2\times42} = \frac{2846}{42} = \frac{2\times1423}{2 \times 21} = \frac{1423}{21}.$$

Answer 3

$$ \frac{ 5692 }{ 84 } = 67 + \frac{ 64 }{ 84 } $$ $$ \frac{ 84 }{ 64 } = 1 + \frac{ 20 }{ 64 } $$ $$ \frac{ 64 }{ 20 } = 3 + \frac{ 4 }{ 20 } $$ $$ \frac{ 20 }{ 4 } = 5 + \frac{ 0 }{ 4 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccc} & & 67 & & 1 & & 3 & & 5 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 67 }{ 1 } & & \frac{ 68 }{ 1 } & & \frac{ 271 }{ 4 } & & \frac{ 1423 }{ 21 } \end{array} $$ $$ $$ $$ 1423 \cdot 4 - 21 \cdot 271 = 1 $$

$$ \gcd( 5692, 84 ) = 4 $$
$$ 5692 \cdot 4 - 84 \cdot 271 = 4 $$