finding GCD using Euclidean

Question

i) Use the Euclidean Algorithm to calculate the greatest common divisor of 95658 and 48685.
Clearly outline all the steps in the algorithm.

(ii) Reverse Euclid’s Algorithm in (i) to find integers x and y so that
gcd(95658, 48685) = 95658x + 48685y.

 

 

 

i have the first one but just not too sure.

Answer 1

Here's i)

95,658-48,685=46,973

48,685-46,973=1712

now find the GCD of 1712 and 46,973 because 1712 is small enough to factor

1712/2=856

856/2=428

428/2=214

214/2=107

1712=2*2*2*2*107

46,973 is odd and not divisible by 2, so divide 46,973 by 107

46,973/107=439

therefore 107 is the GCD of 1712 and 46,973 and therefore 107 is the GCD of 95,658 and 48,685

here is the prime factorization of each number to compare methods:

95,658=2*3*107*149

48,685=5*7*13*107

GCD=107