# Use Euclid's algorithm to find HCF of 1190 and 1445.

Question:

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

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 \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

$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)-[1190-(1445-1190) \times 4]$

$\Rightarrow 85=(1445-1190)-[1190-1445 \times 4+1190 \times 4]$

$\Rightarrow 85=1445-1190-[1190 \times 5-1445 \times 4]$

$\Rightarrow 85=1445-1190-1190 \times 5+1445 \times 4$

$\Rightarrow 85=1445 \times 5-1190 \times 6$

Or, $85=1190(-6)+1445(5)$

Hence, $m=-6, n=5$