<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

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&amp;=&amp;12.4+9\\ 12&amp;=&amp;9.1+3\\ 9&amp;=&amp;3.3+0
\end{eqnarray*}

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

Substituting back,

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

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

\item[(ii)]

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

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

Substituting back

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

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

\end{description}





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