\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

Find all the solutions of each of the following congruences,
expressing your answers in terms of congruence classes, $[x]$:

\begin{description}

\item[(i)]
$7x\equiv29$ (modulo 64),

\item[(ii)]
$3x^5+x^3+3001\equiv9$ (modulo 14).

\end{description}



ANSWER

\begin{description}

\item[(i)]
Since 7 is odd, the residue class $[7]$ represent a unit modulo
64. Hence we need only find the unique $[y]\in U_{64}$ such that
$[x][y]=[1]$ and then the unique solution to (1) is $[x]=[29y]\in
U_{64}$. Since $7^2=49=3\times16+1$ we see that $y=16k+7$ for some
integer $k$. Now consider the congruence

$$7\times(16K+7)=1+16(7k+3) \textrm{ (modulo 64)}.$$

If we choose $7k+3$ to be a multiple of 4 then we have a suitable
solution for $y$. The smallest convenient value is $k=3$ and
$y=55$. Hence the only solution is $x\equiv29\times55\equiv59$
(modulo 64) of $[x]=[59]\in U_{64}$.

\item[(ii)]
We begin by finding all the solutions to this congruence modulo 2
and 7. Modulo 2 all $x$ will yield a solution, Modulo 7 there is
no solution if $x\equiv0$ (modulo 7) since
$3001\equiv201\equiv61\equiv5$ (Modulo7). If $x=1,2,4$ then
$x^3\equiv1$ (modulo 7) while if $x= 3,5,6$ then $x^3\equiv-1$
(modulo 7). Therefore, if $x=1,2,4$, we are trying to solve
$3x^5\equiv9-5-1\equiv2-6\equiv3$ (modulo 7). On the other hand
$x^6\equiv1$ (modulo 7) so that the solutions to this are
$3\equiv3x^6\equiv3x^5x\equiv3x$ (modulo 7) or $x\equiv1$ (modulo
7). On the other hand, if $x=3,5,6$ a similar argument shows that
$3x^5\equiv9-5+1\equiv2-4\equiv5$ (modulo 7). Multiplying by $x$
yields $3\equiv3x^6\equiv3x^5x\equiv 5x$ (modulo 7). The solution
to this is $x\equiv2$ (modulo 7) which is not one of $x=3,5,6$ so
there is no such solution.

Hence we have shown that all the solutions must lie in the set of
integers $\{1+7k|k$ an integer\} which give the two residue
classes $[1], [8]$ (modulo 14).

\end{description}





\end{document}