Question

Find H.C.F of $81$ and $237$.

Also express it as a linear combination of $81$ and $237$ i.e, H.C.F of $81,237=81x+237y$ for some $x,y$.

[Note: Values of $x$ and $y$ are not unique]

Answer 1

According to the definition of Euclid's theorem,

$a=b\times q+r$ where $0\le r<b.$

Since $81<237$, let us apply division algorithm to these numbers.
$81|237|2$
$|162|$
$\overline{|75|}$
$\therefore 237=81\times 2+75$ ..... (1)
Since the remainder $75\ne 0$
$\therefore$ we consider the divisor $81$ and the remainder $75$.

Again by division algorithm,
$75\overline{\left)81\right(}1$
$\underset{–}{75}$
$\underset{–}{6}$
$\therefore 81=75\times 1+6$ .... (2)

Again consider divisor $75$ and new remainder $=6$,
$6\overline{\left)75\right(}12$
$\underset{–}{75}$
$\underset{–}{3}$ ... (3)

Again consider divisor $6$ and new remainder $=3$,
By division algorithm,
$3\overline{\left)6\right(}2$
$\underset{–}{6}$
$\underset{–}{0}$
$\therefore 6=3\times 2+0$ ..... (4)
$\therefore$ The remainder $=0$
$\therefore H.C.F.=3$

In order to write $H.C.F.$ in form of $81$ & $237$, we have
$3=75-6\times 12=75-(81-75\times 1)\times 12$
$=75-12\times 81+12\times 75=13\times 75-12\times 81$
$=13\times (237-81\times 2)-12\times 81$
$=13\times 237-26\times 81-12\times 81$
$=13\times 237-38\times 81$
Thus $3=237y+81x$ where $y=13$ and $x=-38$