Question

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

Answer 1

Using Euclid's division algorithm, we have


Since 1445 > 1190, we apply Euclid's division lemma to 1445 and 1190 to get;
$1445=1190\times 1+255$
Since the remainder is not zero, we again apply division lemma to 1190 and 255 and get;
$1190=255\times 4+170$
Again, the remainder is not zero, so we apply division lemma to 255 and 170 to get;
$255=170\times 1+85$
Now we finally apply division lemma to 170 and 85 to get;
$170=85\times 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
$$\begin{gathered} 170\times 1+85=255 \\ \Rightarrow 85=255-170\times 1 \\ \Rightarrow 85=(1445-1190\times 1)-(1190-255\times 4) \\ \Rightarrow 85=(1445-1190)-\left[1190-(1445-1190)\times 4\right] \\ \Rightarrow 85=(1445-1190)-\left[1190-1445\times 4+1190\times 4\right] \\ \Rightarrow 85=1445-1190-\left[1190\times 5-1445\times 4\right] \\ \Rightarrow 85=1445-1190-1190\times 5+1445\times 4 \\ \Rightarrow 85=1445\times 5-1190\times 6 \end{gathered}$$
Or, $85=1190(-6)+1445\left(5\right)$
Hence, $m=-6,n=5$