Question

How to express HCF of 1190 and 1445 in the form of 1190m+1445n using Euclid's algorithm?

Answer 1

We know that Euclid's division Lemma is x and y for any two positive integers, there exist unique integers q and r satisfactorily x = yq + r, where 0 ≤ r <y.
In case r=0 then y will be the HCF.

1445=1190×1+255
1190=255×4+170
255=170×1+85
170=85×2+0

We have found r=0
Hence, HCF(1190,1445)=85

So, now
85 = 255 - 170

[Put 255=1445-1190 and 170=1190-1020]

85=(1445-1190)-(1190-1020)

[Put 1020=255×4]

85=(1445-1190)-(1190 - 255×4)

[Open brackets,]

85=1445-1190-1190+(255×4)

[Put 255= 1445-1190]

85=1445-(2×1190)+(1445-1190)×4

85=1445-(2×1190)+(1445×4) - (1190x4)

85=1445+(1445×4) - (2×1190) - (1190×4)

85 =(1445×5) - (1190×6)

85= -1190×6 + 1445×5

85=1190×(-6)+1445×5

85=1190m+1445n

(where m=-6 and n=5)