Question

Find the H.C.F of the following pairs of integers and express it as a linear combination of them.
(i) 963 and 657 (ii) 592 and 252 (iii) 506 and 1155 (iv) 1288 and 575

Answer 1

Hint: We first try to find the H.C.F of the given pair of integers using the usual factorisation method. We take the multiplication of the divisors to find the H.C.F. Then we use the linear combination of x, y with G.C.D being c to form the equation $c=ax+by$, where $a,b\in \mathbb{Z}$.

Complete step by step answer:
To find the H.C.F of a pair of integers, we need to keep dividing the numbers with the number that divides both of them and at the end we need to take multiple of those divisors.
H.C.F defines the highest common factor.
Now to find the linear combination of x, y with G.C.D being c, we need to find a, b for the c in such a way that $c=ax+by$, where $a,b\in \mathbb{Z}$.
For 963 and 657 we find their factors and then find the highest common factor
Factors of 963 are $1,3,9,107,321,963$. Factors of 657 are $1,3,9,73,219,657$.
The highest common factor is 9. We can also express H.C.F as
\[\begin{align}
  & 3\left| \!{\underline {\,
  963,657 \,}} \right. \\
 & 3\left| \!{\underline {\,
  321,219 \,}} \right. \\
 & 1\left| \!{\underline {\,
  107,73 \,}} \right. \\
\end{align}\]
The H.C.F will be $3\times 3=9$.
The linear combination will be $9=\left( -15 \right)\left( 963 \right)+\left( 22 \right)\left( 657 \right)$. Here a and b are -15, 22 respectively.
For 592 and 252 we find their factors and then find the highest common factor
Factors of 592 are $1,2,4,8,16,37,74,148,296,592$. Factors of 252 are $1,2,3,4,6,7,9,12,14,18,21,28,36,42,63,84,126,252$.
The highest common factor is 4. We can also express H.C.F as
\[\begin{align}
  & 2\left| \!{\underline {\,
  592,252 \,}} \right. \\
 & 2\left| \!{\underline {\,
  296,126 \,}} \right. \\
 & 1\left| \!{\underline {\,
  148,63 \,}} \right. \\
\end{align}\]
The H.C.F will be $2\times 2=4$.
The linear combination will be $4=\left( -20 \right)\left( 592 \right)+\left( 47 \right)\left( 252 \right)$. Here a and b are -20, 47 respectively.
For 506 and 1155 we find their factors and then find the highest common factor
Factors of 506 are $1,2,11,22,23,46,253,506$. Factors of 1155 are $1,3,5,7,11,15,21,33,35,55,77,105,165,231,385,1155$.
The highest common factor is 11. We can also express H.C.F as
\[\begin{align}
  & 11\left| \!{\underline {\,
  1155,506 \,}} \right. \\
 & 1\left| \!{\underline {\,
  105,46 \,}} \right. \\
\end{align}\]
The H.C.F will be 11.
The linear combination will be $11=\left( -7 \right)\left( 1155 \right)+\left( 16 \right)\left( 506 \right)$. Here a and b are -7, 16 respectively.
For 1288 and 575 we find their factors and then find the highest common factor
Factors of 1288 are $1,2,4,7,8,14,23,28,46,56,92,161,184,322,644,1288$. Factors of 575 are $1,5,23,25,115,575$.
The highest common factor is 23. We can also express H.C.F as
\[\begin{align}
  & 23\left| \!{\underline {\,
  1288,575 \,}} \right. \\
 & 1\left| \!{\underline {\,
  56,25 \,}} \right. \\
\end{align}\]
The H.C.F will be 23.

The linear combination will be $23=\left( -4 \right)\left( 1288 \right)+\left( 9 \right)\left( 575 \right)$. Here a and b are -4, 9 respectively.

Note: We also could have used the Euclidian’s algorithm to find the G.C.D and the linear combination in one go. In that process we try to divide the bigger number by the smaller number to find the remainder and then divide the dividend with the remainder. We continue this process till we find 0 as a remainder.