Question

Find the HCF of the following pair of integers and express it as a linear combination of them.
$963$ and $657$

Answer 1

We can use Euclid division linear to find

$HCF$ of $963$ and $657$

$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$

Since Remainder $=0$

$\therefore HCF(963,657)=9$

Now, we do backward calculation $\Rightarrow$

$9=45-36$

$9=45-(306-45\times 6)$

$9=45\times 7-306$

$9=(657-306\times 2)\times 7-306$

$9=657\times 7-306\times 15$

$9=657\times 7-(963-657)\times 15$

$9=657\times 22-963\times 15$

$\therefore 9=657\times 22-963\times 15$

$HCF(657$, $963)$ as their linear combination