<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 gcd(16169,22747).

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

$$16169x+22747y=69.$$

\end{description}



ANSWER

\begin{description}

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

\begin{eqnarray*}
22747&amp;=&amp;1\times16169+6578\\ 16169&amp;=&amp;13156+3013=2\times6578+3013\\
6578&amp;=&amp;6026+552=2\times3013+552\\ 3013&amp;=&amp;2760+253=5\times552+253\\
552&amp;=&amp;2\times253+46\\ 253&amp;=&amp;5\times46+23\\ 46&amp;=&amp;2\times23
\end{eqnarray*}

so that gcd$(16169,22747)=23$

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

From the Euclidean algorithm in (i)

\begin{eqnarray*}
23&amp;=&amp;253-5\times46\\ &amp;=&amp;253-5\times(552-2\times253)\\
&amp;=&amp;11\times253-5\times552\\&amp;=&amp;11\times(3013-5\times552)-5\times552\\
&amp;=&amp;11\times3013-60\times552\\
&amp;=&amp;11\times3013-60\times(6578-2\times3013)\\&amp;=&amp;131\times3013-60\times6578\\
&amp;=&amp;131\times(16169-2\times6578)-60\times6578\\
&amp;=&amp;131\times16169-322\times6578\\
&amp;=&amp;131\times16169-322\times(22747-16169)\\
&amp;=&amp;453\times16169-322\times22747
\end{eqnarray*}

Hence one solution is $x=3\times453,\ y=-3\times332$. Therefore
the general solution is

$$x=3\time453+3\times\left(\frac{22747n}{23}\right),\
y=-3\times332-3\times\left(\frac{16169n}{23}\right)$$

where $n$ is an arbitrary integer.

\end{description}




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