Question

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

Answer 1

Hint:- In this question use the Euclid's Division lemma which states that ${\text{dividend = divisor}} \times {\text{quotient + remainder}}$ where we continuously use this formula until the remainder becoming zero.
Complete step-by-step solution -
Given integers are $81$ and $237$ such that $237 > 81$
Now apply Euclid's Division lemma i.e. ${\text{dividend = divisor}} \times {\text{quotient + remainder}}$ on $237$ and $81$ we get:
$237 = 81 \times 2 + 75$...... take this as equation first
Here remainder first is $75$ and this is not equals to zero
So further we will apply Euclid's lemma considering $81$ as divisor and $75$ as remainder we get:
$81 = 75 \times 1 + 6$.....take this as equation second
Here remainder is $6$ and this is also not equals to zero
Further we consider new divisor as $75$ and new remainder as $6$ and we will apply Euclid's lemma we get:
$75 = 6 \times 12 + 3$....take this as equation third
Here remainder is $3$ which is also not equals to zero
Again we consider $6$ as divisor and $3$ as remainder and will apply Euclid's lemma we get:
$6 = 3 \times 2 + 0$.....take this as equation fourth
Now the remainder at this stage comes zero which means the divisor at this stage or the remainder at the previous stage i.e. $3$ is the HCF of $81$ and $237$.
Now write below the equation third:
$
  75 = 6 \times 12 + 3 \\
  \therefore 3 = 75 - 6 \times 12 \\
$
Now replacing above $6$, for this we will use equation second which can also be written as
$6 = 81 - 75 \times 1$
$
  \therefore 3 = 75 - \left( {81 - 75 \times 1} \right) \times 12 \\
  3 = 75 - 81 \times 12 + 75 \times 12 \\
  3 = 75 \times 13 - 81 \times 12 \\
$
Now replacing above $75$ , for this we will use equation first which can also be written as:
\[75 = 237 - 81 \times 2\]
$
  \therefore 3 = \left( {237 - 81 \times 2} \right) \times 13 - 81 \times 12 \\
  3 = 237 \times 13 - 81 \times 26 - 81 \times 12 \\
  3 = 237 \times 13 - \left( {26 + 12} \right)81 \\
  3 = 237 \times 13 - 38 \times 81 \\
$
$\therefore 3 = 237x - 81y$
Therefore our coefficients are $13$ and $ - 81$ i.e. $x = 13$ and $y = - 38$
Hence we expressed the HCF of two positive integers as a linear combination.

Note:- In this question we applied the Euclid's Division lemma till our remainder is zero, therefore equation fourth is showing that the value of remainder is zero and from this we concluded that $3$ is the HCF of $81$ and $237$ after that in equation third we substituted the values from equation second and first and got the final equation as $3 = 237 \times 13 - 38 \times 81$ hence found the value of coefficients as $13$ and $ - 81$ and expressed the HCF of two positive integers as a linear combination.