Answer to Question #319092 in Discrete Mathematics for Pravin

Question

1.    Use the Euclidean algorithm to find the greatest common divisor (gcd) of each pairs of integers. Show the steps of calculation.

a) (900,140)                                                                                                         

b) (128,729)

Answer 1

$a:\\900=6\cdot 140+60\\140=2\cdot 60+20\\60=3\cdot 20\\gcd\left( 900,140 \right) =20\\b:\\729=5\cdot 128+89\\128=1\cdot 89+39\\89=2\cdot 39+11\\39=3\cdot 11+6\\11=1\cdot 6+5\\6=1\cdot 5+1\\gcd\left( 128,729 \right) =1$