Question

If $d$ is the $HCF$ of $56$ and $72,$ find $x,y$ satisfying $d=56x+72y.$ Also, show that $x$ and $y$ are not unique.

Answer 1

Applying Euclids division lemma to $56$ and $72$, we get
$72=56\times 1+16$

Since the remainder $16\ne 0$. So, we consider the divisor $56$ and remainder $16$ and apply division lemma to get
$56=16\times 3+8$ ..........$\left(ii\right)$

We consider the divisor $16$ and the remainder $8$ and apply division algorithm to get
$16=8\times 2+0$

We observe that the remainder at this stage is zero. Therefore, last divisor $8$ (or the remainder at the earlier stage) is the $HCF$ of $56$ and $72$.

From $\left(ii\right)$, we get
$8=56-16\times 3$
$\Rightarrow 8=56-(72-56\times 1)\times 3$
$\Rightarrow 8=56-3\times 72+56\times 3$
$\Rightarrow 8=56\times 4+(-3)\times 72$
$\therefore x=4$ and $y=-3$.

Now,$8=56\times 4+(-3)\times 72$
$\Rightarrow 8=56\times 4+(-3)\times 72-56\times 72+56\times 72$
$\Rightarrow 8=56\times 4-56\times 72+(-3)\times 72+56\times 72$
$\Rightarrow 8=56\times (4-72)+\{(-3)+56\}\times 72$
$\Rightarrow 8=56\times (-68)+\left(53\right)\times 72$
$\therefore x=-68$ and $y=53$.

Hence $x$ and $y$ are not unique.