Question

Express the HCF of \[1650\] and \[847\] as a linear combination of \[1650\]and \[847\]?

Answer 1

Hint: In this problem, we will use Euclid Division Lemma to find the HCF of \[1650\] and \[847\].
Then we will express it in the form of a linear combination\[1650x + 847y\].
 i.e. we need to find the values of x and y .

Complete step-by-step answer:
 First we apply the Euclid division algorithm to find HCF of \[1650\] and \[847\].
On dividing 1650 by 847 we get 1 as quotient and 803 as remainder. This is continued as follow:
\[
  1650 = 847 \times 1 + 803 \\
  847 = 803 \times 1 + 44 \\
  803 = 44 \times 18 + 11 \\
  44 = 11 \times 4 + 0 \\
 \]
Now when \[44\]is divided by \[44\] , \[0\] is obtained as remainder . Therefore the remainder in the previous step is the required HCF.
Hence, HCF of \[1650 \] and \[847 \] is \[11\]
Now we will express this HCF as a linear combination of \[1650 \]and \[847 \].
\[
  11 = 803 - 44 \times 18 \\
  11 = 803 - \left( {847 - 803 \times 1} \right) \times 18 \\
 \]
On simplifying we have
\[
  11 = 803 \times 19 - 847 \times 18 \\
  11 = \left( {1650 - 847 \times 1} \right) \times 19 - 847 \times 18 \\
 \]
On simplification, we get HCF of 1650 and 847 as a linear combination of \[1650 \] and \[847 \].
\[11 = 1650 \times 19 - 847 \times 37\].
On comparing the above equation with \[11 = 1650x + 847y\] , we get
Therefore, \[x = 19 \]and \[y = - 37\]
Hence, Express the HCF of \[1650\] and \[847\]as linear combination of \[1650\]and \[847\] , then we get \[x = 19 \] and \[y = - 37\]

Note: HCF stands for highest common factor. It is always less than the given number. Euclid division lemma is used to find the HCF of any two numbers.
When the remainder is 0, then the divisor is the HCF of the given two numbers.
Expressing in the form of linear combination is the reverse process of Euclid division lemma. In this process we revert the steps and move from bottom to top as in euclid division lemma. then we eliminate other numbers except those we need to find the HCF.
The values of x and y thus obtained is the linear combination of the numbers in HCF.