Question

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

Answer 1

Hint: To solve this question, we will use Euclid’s Division lemma. We will consider the greater term as dividend and the smaller term as a divisor. Then we will use this formula until we get our remainder as zero. After getting remainder as zero, we will find the linear combination substituting values from the different expression of Euclid’s lemma.
Formula Used:
According to Euclid’s division lemma,
 $ {\rm{Dividend}} = {\rm{Divisor}} \times {\rm{quotient}} + {\rm{Remainder}} $

Complete step-by-step answer:
The given numbers are 81 and 237. We know that 237 is greater than 81, hence 237 is dividend and 81 is divisor in Euclid’s division lemma. This can be expressed as:
 $ 237 = 81 \times 2 + 75 $ …….(i)
We have 75 as remainder, now 81 will become dividend and 75 will be divisor for Euclid’s division Lemma. This can be expressed as:
 $ 81 = 75 \times 1 + 6 $ ……(ii)
We have 6 as remainder, now 75 will become dividend and 6 will be divisor for Euclid’s division Lemma. This can be expressed as:
 $ 75 = 6 \times 12 + 3 $ ……(iii)
We have 3 as remainder, now 6 will become dividend and 3 will be divisor for Euclid’s division Lemma. This can be expressed as:
 $ 6 = 3 \times 2 + 0 $ ……(iv)
Since we got remainder as zero. We will stop here only. Hence the divisor for the last step or remainder of the third stage is the HCF of the numbers 81 and 237.
Rewriting the equation (iii)
 $
75 = \left( {6 \times 12} \right) + 3\\
3 = 75 - \left( {6 \times 12} \right)
 $
We will replace 6 in the above expression, from equation (ii)
 $ 6 = 81 - 75 \times 1 $
This can now be expressed as
 $
3 = 75 - \left( {81 - 75 \times 1} \right) \times 12\\
3 = 75 - \left( {81 \times 12} \right) + \left( {75 \times 12} \right)\\
3 = 75\left( {1 + 12} \right) - \left( {81 \times 12} \right)\\
3 = 75 \times 13 - 81 \times 12
 $
We will replace 75 from equation(i) as
 $ 75 = 237 - \left( {81 \times 2} \right) $
This can be expressed as:
 $ 3={237-(81\times 2)}\times 13-81 \times 12\\
3=(237\times 13)-(81 \times 26)-(81 \times 12) \\
3= 237 \times 13-81 \times 38\;
 $
This can be expressed as
 $ 3=237x-81y $
From the above expression, we have a coefficient as 13 and , that is $ x = 13 $ and $ y = - 38 $ .
This is the expression of HCF as a linear combination.

Note: We have used Euclid’s division lemma until the remainder comes out to be zero. The fourth equation is the desired equation. From the fourth equation, we came to know that 3 is the HCF of the solution. We then substitute the values from other equations to find expressions as a linear combination.