\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

For each of the following congruences, decide whether or not a
solution exists. If a solution does exist, find all possible
solutions, describing them as congruence classes.

\begin{description}

\item[(i)]
$3x\equiv5$ mod 7.

\item[(ii)]
$12x\equiv15$ mod 22.

\item[(iii)]
$19x\equiv42$ mod 50.

\item[(iv)]
$18x\equiv42$ mod 50.

\end{description}



ANSWER

\begin{description}

\item[(i)]
gcd93,7)=1, which divides 5, so by theorem 3.5 end corollary 3.6,
this congruence has solutions, which form a single congruence
class mod 7.

Multiplying the congruence through by 2 gives $6x\equiv10\equiv3$
mod 7, that is $-x\equiv3$ mod 7, so that $x\equiv-3\equiv 4$ mod
7.

(Alternatively, use $3x\equiv5\equiv12$ mod 7, and then divide
through by 3.)

\item[(ii)]
gcd(12,22)=2 which does not divide 15, so by theorem 3.5 this
equation has no solutions.

\item[(iii)]
gcd(12,22)=1, which divides 42, so solutions exist, and by cor.6.3
they form a single congruence class mod 50.

Multiplying the congruence through by 3 gives $57x\equiv 3.42$ mod
50, that is $7x\equiv3.42$ mod 50, which upon division by 7 yields
$x\equiv3.6\equiv18$ mod 50. (Again, alternative methods exist-
maybe you found a quicker one?)

\item[(iv)]
gcd(18,50)=2, which divides 42, so by theorem 3.5, solutions
exist, and fall into two congruence classes mod 50. If $x_0$ gives
on class of solutions, $x_0+\frac{50}{2}=x_0+25$ gives the other.
Thus we need only one integer $x_0$ satisfying the congruence. The
two congruence classes of solutions will be those with
representatives $x_0$ and $x_0+25$. If $18x\equiv42$ mod 50, then
dividing the whole equation ( including the modulus) through by 2
(see lemma 3.4(i)) gives $9x\equiv21$ mod 25. Multiplying by 3
then gives $27x\equiv 21.3\equiv(-4).3\equiv-12$ mod 25, which
gives $2x\equiv -12$ mod 25. We may now divide by 2 to get
$x\equiv-6\equiv 19$ mod 25. Thus the solutions of the original
equation are $x\equiv19$ mod 50 and $x\equiv 44$ mod 50.

\end{description}




\end{document}