\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&=&1\times16169+6578\\ 16169&=&13156+3013=2\times6578+3013\\
6578&=&6026+552=2\times3013+552\\ 3013&=&2760+253=5\times552+253\\
552&=&2\times253+46\\ 253&=&5\times46+23\\ 46&=&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&=&253-5\times46\\ &=&253-5\times(552-2\times253)\\
&=&11\times253-5\times552\\&=&11\times(3013-5\times552)-5\times552\\
&=&11\times3013-60\times552\\
&=&11\times3013-60\times(6578-2\times3013)\\&=&131\times3013-60\times6578\\
&=&131\times(16169-2\times6578)-60\times6578\\
&=&131\times16169-322\times6578\\
&=&131\times16169-322\times(22747-16169)\\
&=&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}