\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

Find all possible simultaneous solutions to the following sets of
congruences, expressing your answers as congruence classes modulo
some suitable integer.

\begin{description}

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

$x\equiv 7$ mod 9.

$x\equiv 3$ mod 4.

\item[(ii)]
$x^2+2x+2\equiv0$ mod 5.

$7x\equiv 3$ mod 11.

\end{description}



ANSWER

\begin{description}

\item[(i)] 7,9 and 4 are mutually coprime, so the Chinese
Remainder Theorem guarantees a solution, which is unique mod
$7.9.4=252$, You may have followed the method of the Chinese
Remainder Theorem, or gone for the quick method. Here are
solutions for both:-

CHINESE REMAINDER THEOREM

Here $n=7.9.4-252,\ N_1=\frac{n}{7}=36,\ N_2=\frac{n}{9}=28$ and
$N_3=\frac{n}{4}=63$. We must solve $36x_1\equiv1$ mod 7,
$28x_2\equiv1$ mod 9 and $63x_3\equiv1$ mod 4. These simplify to
$x_1\equiv 1$ mod 7, $x_2\equiv1$ mod 9 and $-x_3\equiv1$ mod 4,
so we may take $x_1=1,x_2=1$ and $x_3=3$. The Chinese Remainder
Theorem then tells us that $\overline{x}=2.36.1+7.28.1+3.63.3$ is
a simultaneous solution. Now $\overline{x}=72+196+567=835\equiv79$
mod 252 so our solution is $x\equiv79$ mod 252.

QUICK METHOD

The Chinese Remainder Theorem guarantees a congruence class of
solutions mod 252, so guarantees integer solutions bigger than any
pre-ordained size.

We start with the equation of largest modulus, $x\equiv7$ mod 9,
find an integer soluytion (7), then increase it by multiples of 9
until we reach a solution of the next congruence $x\equiv2$ mod 7,
viz. 7,16.

16 is a common solution of $x\equiv7$ mod 9 and $x\equiv 2$ mod 7.
We increase this by multiples of 9.7 ( so that the numbers on our
list are solutions to both equations), until we reach a solution
of the final equation, $x\equiv3$ mod 4, viz. 16, 79.

Thus $x\equiv79$ mod 252 simultaneously solves all three
equations.

\item[(ii)]
We begin by solving the congruences:

For $x^2+2x+2\equiv0$ mod 5 we have not yet learnt a general
method (see $\S$7), but as 5 is small , we may try out all
congruence classes mod 5, and pick out the solutions. The least
absolute residues mod 5 are $0,\pm1,\pm2,$ and we see that
$f(0)\equiv2$ mod 5,$f(1)=5\equiv0$ mod 5, $f(-1)\equiv1$ mod 5,
$f(2)=10\equiv0$ mod 5 and $f(-2)\equiv2$ mod 5, so the solutions
of the congruence are $x\equiv1$ mod 5 and $x\equiv2$ mod 5.

To solve $7x\equiv3$ mod 11, we could use, for example,
$7x\equiv3\equiv14$ mod 11, so on division by 2, $x\equiv2$ mod
11.

Thus a simultaneous solution of both congruences would satisfy
either $x\equiv1$ mod 5 and $x\equiv2$ mod 11 or $x\equiv2$ mod 5
and $x\equiv2$ mod 11.

The Chinese Remainder Theorem guarantees a unique solution for eac
pair of equations mod 55, so we will end up with two congruence
classes mod 55 as solutions. Again we have a choice of two
methods- this time I'll use the quick method:-

For $x\equiv1$ mod 5 and $x\equiv2$ mod 22, start with a solution
(2) for $x\equiv2$ mod 11, and increase by multiples of 11 until
we reach a solution of $x\equiv1$ mod 5.

We get 2,13,24,35,46, so a suitable solution is $x\equiv 46$ mod
55.

For $x\equiv2$ mod 5 and $x\equiv 2$ mod 11, we immediately see
(as the solution is unique mod 55) that $x\equiv2$ is the answer.

Thus the two congruences are solved by either $x\equiv2$ or
$x\equiv 46$ mod 55.

\end{description}




\end{document}