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 '18 at 18:05
  • $\begingroup$ Oh, sorry. I didn't see that. $\endgroup$ Aug 26 '18 at 18:06
  • 3
    $\begingroup$ You don't have to factorise two numbers to find their gcd. Use the Euclidean Algorithm. $\endgroup$ Aug 26 '18 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 '18 at 18:08
  • 1
    $\begingroup$ Possible duplicate of Euclidean Algorithm vs Factorization $\endgroup$ Aug 26 '18 at 18:10
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.