Question

Find gcd(31415,14142) by applying euclid's algorithm
b.estimate how many times faster it will be to find gcd(31415,14142) by

Answer 1

$31415=2\cdot14142+3131$
$14142=4\cdot3131+1618$
$3131=1\cdot1618+1513$
$1618=1\cdot1513+105$
$1513=14\cdot105+43$
$105=2\cdot43+19$
$43=2\cdot19+5$
$19=3\cdot5+4$
$5=1\cdot4+1$
$\implies\mathrm{gcd}(31415,14142)=1$