Question

using euclids division algorithm find the largest number that divides 1257,9377,and 15628 leaving remainders 1,2,and 3 respectively.

Answer 1

1257-1= 1256
9377-2= 9375
15628-3= 15625

hcf (1256,9375,15625)
hcf(15625,9375)

15625 is greater than 9375
15625= 9375×1+6250
9375 is greater than 6250
9375= 6250× 1+3125
6250 is greater than 3125
6250= 3125×2+0
therefore ,
hcf (15625,9375)= 3125


now,
hcf( 3125,1256)
3125 is greater than 1256
3125= 1256×2+613
1256 is greater than 613
1256= 613× 1+ 30
613 is greater than 30
613= 30×20+13
30= 13×2+4
13=4×3+1
4= 1×4+0