Question

Use the euclidean algorithm to find

Answer 1

A)
$18=1\cdot12+6$
$12=2\cdot6+0$
$\implies\mathrm{gcd}(12,18)=6$

b)
$201=1\cdot111+90$
$111=1\cdot90+21$
$90=4\cdot21+6$
$21=3\cdot6+3$
$6=2\cdot3+0$
$\implies\mathrm{gcd}(111,201)=3$

c)
$1331=1\cdot1001+330$
$1001=3\cdot330+11$
$330=30\cdot11+0$
$\implies\mathrm{gcd}(1001,1331)=11$

d)
$54321=4\cdot12345+4941$
$12345=2\cdot4941+2463$
$4941=2\cdot2463+15$
$2463=164\cdot15+3$
$15=5\cdot3+0$
$\implies\mathrm{gcd}(12345,54321)=3$

e)
$5040=5\cdot1000+40$
$1000=25\cdot40+0$
$\implies\mathrm{gcd}(1000,5040)=40$

f)
$9888=1\cdot6060+3828$
$6060=1\cdot3828+2232$
$3828=1\cdot2232+1596$
$2232=1\cdot1596+636$
$1596=2\cdot636+324$
$636=1\cdot324+312$
$324=1\cdot312+12$
$312=26\cdot12+0$
$\implies\mathrm{gcd}(9888,6060)=12$