Question

Use euclid's algorithm to find the HCF of 1190 and 1445 Express the HCF in the form of 1190m + 1445n

Answer 1

largest no = smallest no * quotient+ remainder
use the same formula with largest no = current smallest no and remainder as next smallest no(divisor)
continue until remainder = 0. Now the current divisor is the HCF.
1445=1190 x 1 + 255

1190=255 x 4 +170

255=170 x 1 + 85

170=85 x 2 + 0

HCF = 85

Now exapand from the second last step to top and find the coefficients

85 = 255 - 170

=(1445-1190)-(1190-255 x 4)

=1445-1190-1190+255 x 4

=1445-1190 x 2+(1445-1190) x 4

=1445-1190 x 2+1445 x 4-1190 x 4

=1445 x 5 - 1190 x 6

=1190 x (-6) + 1445 x 5

=1190m + 1445n, where m= -6 and n = 5