• Support PF! Buy your school textbooks, materials and every day products Here!

Fraction reduction, euclid's algorithm

  • Thread starter rayman123
  • Start date
  • #1
152
0

Homework Statement


reduce the fraction [tex]\frac{943578}{1978935}[/tex] to its lowest terms using Euclid's algorithm







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
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,777
911
Divide both numerator and denominator by that "greatest common divisor".
 
  • #3
152
0
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?
 

Related Threads for: Fraction reduction, euclid's algorithm

  • Last Post
Replies
5
Views
2K
Replies
1
Views
2K
Replies
5
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
6
Views
295
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
0
Views
1K
Top