# Fraction reduction, euclid's algorithm

## Homework Statement

reduce the fraction $$\frac{943578}{1978935}$$ 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

HallsofIvy
$$\frac{942578}{1978935}=\frac{314526}{659645}$$