0
$\begingroup$

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 ?

$\endgroup$
6
  • $\begingroup$ do you mean $5,692$ ? $\endgroup$ Aug 26, 2018 at 18:05
  • $\begingroup$ Oh, sorry. I didn't see that. $\endgroup$
    – user549013
    Aug 26, 2018 at 18:06
  • 3
    $\begingroup$ You don't have to factorise two numbers to find their gcd. Use the Euclidean Algorithm. $\endgroup$ Aug 26, 2018 at 18:07
  • 1
    $\begingroup$ The Euclidean Algorithm is much faster than, say, the number field sieve for integer factoring. See this question. $\endgroup$ Aug 26, 2018 at 18:08
  • 1
    $\begingroup$ Possible duplicate of Euclidean Algorithm vs Factorization $\endgroup$ Aug 26, 2018 at 18:10

3 Answers 3

2
$\begingroup$

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}.$$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

$$ \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 $$

$\endgroup$

You must log in to answer this question.