Question

Find the HCF of the following pairs of integers and express it as a linear combination of them.

• A. 963 and 657
• B. 592 and 252
• C. 506 and 1155
• D. 1288 and 575

Answer 1

The correct option is A 963 and 657

To express HCF (of 963 and 657) as a linear combination of them means
HCF = 963x + 657y.
Using Euclid Division Lemma we get HCF as 9.
$a=bq+r,0\le r<b$
$963=657\times 1+306$
$657=306\times 2+45$
$306=45\times 6+36$
$45=36\times 1+9$
$36=9\times 4+0$
$\therefore$ HCF (657, 963)=9.
Now we have to express 9 as a linear combination of 963 and 657.
9 = 963x + 657y.
To do this we have to use the relations obtained in finding the HCF using Euclid Division Lemma.

9= 45-36(1) (From 2nd lost step of finding HCF)
$=45–(306-45\times 6)$ (from 3rd step of finding HCF)
$=45-306+45\times 6$
$9=45\times 7-306$
$9=45\times 7-306$
But $45=657-306\times 2$ (From 4th last step)
$\therefore$ $9=(657-306\times 2)7-306$
$=657\times 7-306\times 14-306$
$9=657\times 7-306\times 15$
But 306=963-657 (From 1st step of finding HCF)
$\therefore 9=657\times 7-(963-657)15$
$=657\times 7-963\times 15+657\times 15$
$=657\times 22-963\times 15$
$\therefore 9=(-15)963+22\left(657\right)=963x+657y$.
X=-15, y=22