Question

Find the HCF of 81 and 237.
Also, express it as the linear combination of 81 and 237 i.e. the HCF of 81,237 \[ = 81x + 237y\] for some x and y.
[values of x and y are not unique].

Answer 1

Hint: Here we will apply the Euclid division algorithm to find the HCF of the given numbers and then write it as the linear combination of the two given numbers.
According to the Euclid division algorithm, if a and b are two numbers and \[a > b\]
Then we need to divide a by b and obtain the remainder.
Now if the remainder is not equal to zero then we need to divide b by the remainder and continue the process until the remainder obtained is zero.
When we get the remainder as zero, then the final quotient obtained is the HCF of the two numbers.
Also we form the equations after each division using the division algorithm given by:-
\[{\text{dividend}} = {\text{quotient}}\left( {{\text{divisor}}} \right) + {\text{remainder}}\]
And we will use the equations so formed to write the HCF as the linear combination of the given numbers.

Complete step-by-step answer:
The given numbers are:-
81 and 237
We will apply the Euclid division algorithm to find the HCF of these numbers.
Now since \[237 > 81\]
Hence according to the Euclid algorithm, we will divide 237 by 81
Hence on dividing we get:-
    \[\underline {{\text{ }}} \]
\[81)237(2\]
\[\underline {{\text{ }} - 162{\text{ }}} \]
         \[{\text{75}}\]

Here,
\[{\text{dividend}} = 237\]
\[{\text{quotient}} = 2\]
\[{\text{divisor}} = 81\]
\[{\text{remainder}} = 75\]
Now writing it in the form of an equation using division algorithm we get:-
Since the division algorithm states that:-
\[{\text{dividend}} = {\text{quotient}}\left( {{\text{divisor}}} \right) + {\text{remainder}}\]
Hence putting in the values we get:-
\[237 = 2\left( {81} \right) + 75.......................\left( 1 \right)\]
Now since the remainder obtained in the above division is not zero
Therefore, then we need to divide divisor by the remainder i.e. we need to divide 81 by 75
Hence on dividing we get:-
     \[\underline {{\text{ }}} \]
\[75)81(1\]
\[\underline {{\text{ }} - 75{\text{ }}} \]
      \[{\text{6}}\]
Here,
\[{\text{dividend}} = 81\]
\[{\text{quotient}} = 1\]
\[{\text{divisor}} = 75\]
\[{\text{remainder}} = 6\]
Now writing it in the form of an equation using division algorithm we get:-
Since the division algorithm states that:-
\[{\text{dividend}} = {\text{quotient}}\left( {{\text{divisor}}} \right) + {\text{remainder}}\]
Hence putting in the values we get:-
\[81 = 1\left( {75} \right) + 6.......................\left( 2 \right)\]
Now since the remainder obtained in the above division is not zero
Therefore, then we need to divide divisor by the remainder i.e. we need to divide 75 by 6
Hence on dividing we get:-
   \[\underline {{\text{ }}} \]
\[6)75(12\]
\[\underline {{\text{ }} - 72{\text{ }}} \]
      \[{\text{3}}\]
Here,
\[{\text{dividend}} = 75\]
\[{\text{quotient}} = 12\]
\[{\text{divisor}} = 6\]
\[{\text{remainder}} = 3\]
Now writing it in the form of an equation using division algorithm we get:-
Since the division algorithm states that:-
\[{\text{dividend}} = {\text{quotient}}\left( {{\text{divisor}}} \right) + {\text{remainder}}\]
Hence putting in the values we get:-
\[75 = 12\left( 6 \right) + 3.......................\left( 3 \right)\]
Now since the remainder obtained in the above division is not zero
Therefore, then we need to divide divisor by the remainder i.e. we need to divide 6 by 3
Hence on dividing we get:-
   \[\underline {{\text{ }}} \]
\[3)6{\text{ }}(2\]
\[\underline {{\text{ }} - 6{\text{ }}} \]
   \[{\text{0}}\]
Here,
\[{\text{dividend}} = 6\]
\[{\text{quotient}} = 2\]
\[{\text{divisor}} = 3\]
\[{\text{remainder}} = 0\]
Now writing it in the form of an equation using division algorithm we get:-
Since the division algorithm states that:-
\[{\text{dividend}} = {\text{quotient}}\left( {{\text{divisor}}} \right) + {\text{remainder}}\]
Hence putting in the values we get:-
\[6 = 2\left( 3 \right) + 0.......................\left( 4 \right)\]
Now since we finally got the remainder as zero therefore, the final quotient i.e. 3 is the HCF of 237 and 81.
Now we will write 3as the linear combination of 81 and 237:-
Hence considering equation 3 we get:-
 \[75 = 12\left( 6 \right) + 3\]
Evaluating the value of 3 from this equation we get:-
\[3 = 75 - 12\left( 6 \right)\]……………………..(5)
Now putting the value of 6 from equation 2 we get:-
The equation 2 is given by:-
\[81 = 1\left( {75} \right) + 6\]
Evaluating the value of 6 we get:-
\[6 = 81 - \left( 1 \right)\left( {75} \right)\]
\[ \Rightarrow 6 = 81 - 75\]
Now putting this value in equation 5 we get:-
\[3 = 75 - \left( {81 - 75} \right) \times 12\]
Solving it further we get:-
\[3 = 75 - \left( {81 \times 12} \right) - \left( { - 75 \times 12} \right)\]
\[ \Rightarrow 3 = 75 - \left( {81 \times 12} \right) + \left( {75 \times 12} \right)\]
Now taking 75 as common we get:-
\[3 = 75\left[ {1 + 12} \right] - \left( {81 \times 12} \right)\]
\[ \Rightarrow 3 = 75 \times 13 - \left( {81 \times 12} \right).........................\left( 6 \right)\]
Now putting the value of 75 in above equation from equation1 we get:
The equation1 is given by:-
\[237 = 2\left( {81} \right) + 75\]
Evaluating the value of 75 we get:-
\[75 = 237 - 81 \times 2\]
Putting this value in equation 6 we get:-
\[3 = \left( {237 - 81 \times 2} \right) \times 13 - \left( {81 \times 12} \right)\]
Solving it further we get:-
\[ \Rightarrow 3 = 237 \times 13 - 81 \times 2 \times 13 - 81 \times 12\]
\[ \Rightarrow 3 = 237 \times 13 - 81 \times 26 - 81 \times 12\]
Taking 81 as common we get:-
\[3 = 237 \times 13 - 81\left( {26 + 12} \right)\]
\[ \Rightarrow 3 = 237 \times 13 - 81 \times 38\]
\[ \Rightarrow 3 = 81 \times \left( { - 38} \right) + 237 \times \left( {13} \right)\]
Now since it is given that the linear combination of 81 and 237 is the HCF of 81,237\[ = 81x + 237y\]
Hence comparing the given equation with the above calculated equation we get:
\[x = - 38;y = 13\]

Note: Students should note that in the Euclid algorithm always number is divided by the smaller number.
Also students should continue the process of division until the remainder comes out to be zero and write the HCF accordingly.
While writing the HCF as a linear combination we need to use the equations formed while dividing by the Euclid algorithm.