Question

Find $\mathrm{HCF}$ of $81$ and $237$ and express it as a linear combination of $81$ and $237$ i.e., $\mathrm{HCF}\left(81,237\right)=81x+237y$ for some $x$ and $y.$

Answer 1

The objective is to determine the $\mathrm{HCF}\left(81,237\right)$ and for some $x$ and $y$ express it in linear terms of $81x+237y$.

Step 1 :

Calculating the $\mathrm{HCF}$ by Euclid's division algorithm,

$\begin{array}{rcl}237& =& 2\times 81+75\\ 81& =& 1\times 75+6\\ 75& =& 12\times 6+3\\ 6& =& 3\times 2+0\end{array}$

So, the $\mathrm{HCF}$is $3$

Step 2 :

For the linear terms, start the reverse process.

Here,

$3=75-\left(12\times 6\right)$

Substitute $6$ by $81-\left(1\times 75\right)$,

$\begin{array}{rcl}3& =& 75-12\left[81-\left(1\times 75\right)\right]\\ & =& 75-12\left(81\right)+12\left(75\right)\\ & =& 13\left(75\right)-12\left(81\right)\end{array}$

Finally, substitute $75$ by $237-\left(2\times 81\right)$

$\begin{array}{rcl}3& =& 13\left(237-2\left(81\right)\right)-12\left(81\right)\\ & =& 13\left(237\right)-26\left(81\right)-12\left(81\right)\\ & =& -38\left(81\right)+13\left(237\right)\\ & =& 81x+237y,\mathrm{for}\mathrm{some}x=-38\mathrm{and}\mathrm{y}=13.\end{array}$

Final Answer :

Hence, the $\mathrm{HCF}$is $3$ and for some $x=-38\mathrm{and}y=13$ there is $81x+237y$.