\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

For each of the following pairs $(a,b)$, use the Euclidean
algorithm to find gcd$(a,b)$ and write it in the form $ax+by$ for
suitable integers $x$ and $y$.

\begin{description}

\item[(i)]
$(12,57)$.

\item[(ii)]
$(743,601)$.

\end{description}




ANSWER

\begin{description}

\item[(i)]

\begin{eqnarray*}
57&=&12.4+9\\ 12&=&9.1+3\\ 9&=&3.3+0
\end{eqnarray*}

so gcd(57,12)=last non-zero remainder =3.

Substituting back,

\begin{eqnarray*}
3&=&12-9.1\\&=&12-(57-12.4)\\&=&12.5-57.1
\end{eqnarray*}

so $x=5,\ y=-1$ is a solution.

\item[(ii)]

\begin{eqnarray*}
743&=&601.1+142\\ 601&=&142.4+33\\ 142&+&33.4+10\\ 33&=&10.3+3\\
10&=&3.3+1\\ 3&=&3.1+0
\end{eqnarray*}

so gcd(743,601)=last non-zero remainder=1.

Substituting back

\begin{eqnarray*}
1&=&10-3.3\\ &=&10-(33-10.3).3\\ &=&10.10-33.3\\
&=&(142-33.4).10-33.3\\ &=&142.10-33.43\\
&=&142.10-(601-142.4).43\\ &=&142.182-601.43\\
&=&(743-601.1).182-601.43\\ &=&743.182-601.225
\end{eqnarray*}

so $x=182,\ y=-225$ is a solution.

\end{description}





\end{document}
