Question

Use Euclid’s division algorithm to find the H.C.F of (i) 426 and 575 (ii) 4641 and 11063

Answer 1

Using E.D.A,

575=426x1+149
426=149x2+128
149=128x1+21
128=21x6+2
21=2x10+1
2=1x2+0
Since r=0,
HCF Of 476 and 575 = 1

Using E.D.A,

11063=4641x2+1781
4641=1781x3+1079
1781=1079x1+702
1079=702x1+377
702=377x1+325
377=325x1+52
325=52x6+13
52=13x3+13
13=13x1+0
Since r=0,
HCF Of 4641 and 11063 = 13