<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

\begin{description}

\item[(i)]
Find HCF(1147,851).

\item[(ii)]
Find HCF(148,1147,851)

\item[(iii)]
Find all the integral solutions, $x$ and $y$, to the linear
Diophantine equation

$$1147x+851y=111.$$

\end{description}



ANSWER

\begin{description}

\item[(i)]
We use the Euclidean algorithm

\begin{eqnarray*}
1147&amp;=&amp;1\times851+296\\ 851&amp;=&amp;2\times296+259\\
296&amp;=&amp;1\times259+37\\ 269=7\times37
\end{eqnarray*}

So that HCF(1147, 851)=37.

\item[(ii)]
By part (i), HCF(148,1147,851)=HCF(148,37)=37 since
$148=4\times37$ and 37 is a prime.

\item[(iii)]
To solve this we must first observe that $111=3\times37$ so that
there exists an infinite number of solutions. Next we must find
one.

From the Euclidean algorithm in (i), $296=1147-1\times851$ and
$259=1\times851-2\times(11-1\times851)=3\times851-2\times1147$ so
that

$$37=1147-1\times851-(3\times851-2\times1147)=3\times1147-4\times851.$$

Therefore

$$11=9\times1147-12\times851$$

so that one solution is $x=9, y=-12$ and therefore the general
solution is

$$x=9+\left(\frac{851n}{37}\right),
y=-12-\left(\frac{1147n}{37}\right)$$

where $n$ is an arbitrary integer.

\end{description}




\end{document}
</pre></body></html>