Question

Find the $HCF$ of $81$ and $237$ and express it as a linear combination of $81$ and $237.$

Answer 1

Given integers are $81$ and $237$ such that $81<237$.

Applying division lemma to $81$ and $237$, we get
$237=81\times 2+75$
Since the remainder $75\ne 0$. So, consider the divisor $81$ and the remainder $75$ arndapply division lemma to get
$81=75\times 1+6$
We consider the new divisor $75$ and the new remainder $6$ and apply division lemma to get
$75=6\times 12+3$
We consider the new divisor $6$ and the new remainder $3$ and apply division lemma to get
$6=3\times 2+0$
The remainder at this stage is zero. So, the divisor at this stage or the remainder at the earlier stage i.e. $3$ is the $HCF$ of $81$ and $237$.

To represent the $HCF$ as a linear combination of the given two numbers, we start from the last but one step and successively eliminate the previous remainder as follows:
From $\left(iii\right)$, we have
$3=75-6\times 12$
$\Rightarrow 3=75-(81-75\times 1)\times 12$
$\Rightarrow 3=75-12\times 81+12\times 75$
$\Rightarrow 3=13\times 75-12\times 81$
$\Rightarrow 3=13\times (237-81\times 2)-12\times 81$
$\Rightarrow 3=13\times 237-26\times 81-12\times 81$
$\Rightarrow 3=13\times 237-38\times 81$
$\Rightarrow 3=237x+81y$, where $x=13$ and $y=-38$.

Now the $HCF$ (say d) of two positive integers $a$ and $b$ can be expressed as a linear combination of $a$ and $b$ i.e., $d=xa+yb$ for some integers $x$ and $y$.

Also, this representation is not unique. Because,
$d=xa+yb$
$\Rightarrow d=xa+yb+ab-ab$
$\Rightarrow d=(x+b)a+(y-a)b$

In the above example, we had
$3=13\times 237-38\times 81$
$\Rightarrow 3=13\times 237-38\times 81+237\times 81-237\times 81$
$\Rightarrow 3=(13\times 237+237\times 81)+(-38\times 81-237\times 81)$
$\Rightarrow 3=(13+81)\times 237+(-38-237)\times 81$
$\Rightarrow 3=94\times 237-275\times 81$
$\Rightarrow 3=94\times 237+(-275)\times 81$