history of mathematics by David m burton 15 Find gcd 143 277

*history of mathematics by David m. burton

15. Find gcd (143, 277), gcd (136, 232), and gcd (272, 1479).

277=143*2-9 ,9=143*2-277

143=9*16-1 ,1=9*16-143=31*143-16*277

Hence, gcd(143,277)=1

232=136*2-40, 40 =136*2-232

136=40*3+16, 16=136-40*3=-3*136+2*232

40=16*2+8, 8=40-2*16=136*2-232-2*(-3*136+2*232)=8*136-5*232

16=8*2+0

Hence, gcd(136,232)=8

1479=272*5+119 ,119=1479-272*5

272=119*2+34 , 34=272-2*119=12*275-2*1479

119=34*3+17, 17=119-34*3=1479-5*272-3*(12*275-2*1479)=7*1479-41*272

34=2*17+0

Hence

gcd(272,1479)=17