1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fraction reduction, euclid's algorithm

  1. Sep 2, 2012 #1
    1. The problem statement, all variables and given/known data
    reduce the fraction [tex]\frac{943578}{1978935}[/tex] to its lowest terms using Euclid's algorithm







    3. The attempt at a solution
    I start with finding the gcd of these two numbers using E.algorithm

    1978935=943578*2+91779
    942578=91779*10+25788
    91779=25788*3+14415
    25788=14415*1+11373
    14415=11373*1+3042
    11373=3042*3+2247
    3042=2247*1+795
    2247=795*2+657
    795=657*1+138
    657=138*4+105
    138=105*1+33
    105=33*3+6
    33=6*5+3
    6=2*3+0
    so gcd(1978935,942578)=3
    but here I am somehow unable to use it to reduce the fraction. Please help
     
  2. jcsd
  3. Sep 2, 2012 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Divide both numerator and denominator by that "greatest common divisor".
     
  4. Sep 2, 2012 #3
    I am not sure if this is the way we are supposed to do it...Euclid's algorithm is to help to make the calculations easier, without calculator no one can do such divisions...
    [tex]\frac{942578}{1978935}=\frac{314526}{659645}[/tex]
    but how can we be sure that this is not further reducible?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Fraction reduction, euclid's algorithm
  1. Euclid's Algorithm (Replies: 5)

  2. Euclid's formula (Replies: 3)

Loading...