wiz-icon
MyQuestionIcon
MyQuestionIcon
1
You visited us 1 times! Enjoying our articles? Unlock Full Access!
Question

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

Open in App
Solution

Using Euclid's division algorithm, we have


Since 1445 > 1190, we apply Euclid's division lemma to 1445 and 1190 to get;
1445=1190×1+255
Since the remainder is not zero, we again apply division lemma to 1190 and 255 and get;
1190=255×4+170
Again, the remainder is not zero, so we apply division lemma to 255 and 170 to get;
255=170×1+85
Now we finally apply division lemma to 170 and 85 to get;
170=85×2+0
Since, in this step, 85 completely divides 170 leaving zero remainder, we stop the procedure.
Hence, the HCF is 85.
Now, using the above division, we have
170×1+85=25585=255-170×185=(1445-1190×1)-(1190-255×4)85=(1445-1190)-1190-(1445-1190)×485=(1445-1190)-1190-1445×4+1190×485=1445-1190-1190×5-1445×485=1445-1190-1190×5+1445×485=1445×5-1190×6
Or, 85=1190(-6)+1445(5)
Hence, m=-6, n=5

flag
Suggest Corrections
thumbs-up
5
Join BYJU'S Learning Program
similar_icon
Related Videos
thumbnail
lock
Euclid's Division Algorithm_Tackle
MATHEMATICS
Watch in App
Join BYJU'S Learning Program
CrossIcon