Question :
Use Euclid’s algorithm to find the HCF of 1190 and 1445. Express the HCF in the form
1190m + 1445n.
Solution:
First we will find HCF using the successive division method or Euclid’s division algorithm.
Step I: As 1445 > 1190, we
divide 1445 by 1190 and get 255 as remainder,
by Euclid’s division lemma, we get
1445 = 1190 x 1 + 255 ……………(i)
Step II: Here the remainder,255 is not equal to 0, we divide 1190 by 255 and get 4 as quotient and 170 as remainder, by Euclid’s division lemma, we get
1190 = 255 x 4 + 170 ……………….(ii)
Step III: Here again the remainder is not equal to 0, we divide 255 by 170 and get 1 as quotient and 85 as remainder, by Euclid’s division lemma, we get
255 = 170 x 1 + 85 ………….(iii)
Step IV: Here again the remainder is not equal to 0, we divide 170 by 85 and this time gets remainder 0.
170 = 85 x 2 + 0 …………….(iv)
Now the divisor this time is the HCF of 1190 and 1445
Therefore, HCF (1190, 1445) = 85
Now the second part of the question is to express the HCF in the form of 1190m x 1445n.
For this we will take the equation (iii), as it is the equation in which HCF is left as remainder.
255 = 170 x 1 + 85
Write it in the form of HCF: 85 = 255 – 170 x 1
And solve it to change it in the form of 1190m x 1445n
85 = 255 – 170
85 = 255 + (255 x 4 – 1190) {Sign is changed to positive}
85 = 255 + 255 x 4 – 1190
85 = 255 x 5 – 1190
85 = (1445 – 1190) x 5 – 1190
85 = 1445 x 5 – 1190 x 5 -1190
85 = 1445 x 5 + 1190(-5 -1)
85 = 1190(-6) + 1445(5)
Hence the HCF 85 is written in the form of 1190m x 1445n.
 |
| JK ONLINE CLASSES |
Contact me for online tuition or live homework assistance for math and science from grade 8th to 10th.