Question

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

Answer 1

Step 1 : Find the HCF of given numbers

Given integers are$81$ and $237$such that ,$237>81$

Applying division lemma to $81$and $237$, we get
$237=81\times 2+75$ …….(i)
Since the remainder is $75\ne 0$. So, apply the division lemma to the divisor $81$ and the remainder $75$ to get
$81=75\times 1+6$ ……(ii)
We consider the new divisor $75$ and the new remainder $6$ and apply division lemma, to get
$75=6\times 12+3$ ……(iii)

We consider the new divisor $6$ and the new remainder $3$ and apply division lemma, to get
$6=3\times 2+0$ ……(iv)
At this stage the remainder is zero. So, that last divisor or the non-zero remainder at the earlier stage i.e. $3$is the HCF of $81$ and $237$.

Step 2 : Express the HCF in the form of a linear combination of the given numbers

Given numbers: $81$ and $237$.

Rewriting the equation (iii)
$$\begin{gathered} 75=\left(6\times 12\right)+3 \\ \Rightarrow 3=75-\left(6\times 12\right) \end{gathered}$$

By replacing $6$ in the above expression, from equation (ii)
$$\begin{gathered} \Rightarrow 3=75-\left(81-75\times 1\right)\times 12 \\ \Rightarrow 3=75-\left(81\times 12\right)+\left(75\times 12\right) \\ \Rightarrow 3=75\left(1+12\right)-\left(81\times 12\right) \\ \Rightarrow 3=75\times 13-81\times 12 \end{gathered}$$

By replacing $75$ from equation(i) as
$$\begin{gathered} \Rightarrow 3=237-(81\times 2)\times 13-81\times 12 \\ \Rightarrow 3=(237\times 13)-(81\times 26)-(81\times 12) \\ \Rightarrow 3=237\times 13-81\times 38 \\ \Rightarrow 3=237\times \left(13\right)+81\times \left(-38\right) \end{gathered}$$
$\Rightarrow 3=237x+81y$, where $x=13$ and $y=-38$.

Hence, the HCF of$81$ and $237$ is $3$and the linear combination can be expressed as $3=237x+81y$, where $x=13$ and $y=-38$.