How to find all solutions to system of congruences with Chinese Remainder Theorem?

Question

This is from Discrete Mathematics and its Applications

Here is my work so far

gcd(3, 4) = 1 $\,$gcd(3, 5) = 1$\,$gcd(4,5) = 1

$\quad$ mod 3 $\quad$ mod 4 $\quad$mod 5
x $\equiv$ 4 * 5$\qquad$3 * 5 * 3 $\quad$ 3 * 4 * 4

Applying mod 3 to everything, you get x $\equiv$ 20$\equiv$2 (mod 3), which matches up
Applying mod 4 to everything, you get x $\equiv$ 15$\equiv$3 (mod 4), which doesn't match up with
x $\equiv$2 (mod 3) so i multiplied 15 by 3 to get 45, meaning x $\equiv$ 45$\equiv$1 (mod 4)
And finally after applying mod 5 to everything, you get x $\equiv$ 12$\equiv$2 (mod 5), which doesn't match up with x $\equiv$3 (mod 5) so I multiplied 12 by 4 to get 48, meaning x $\equiv$ 48$\equiv$3 (mod 5).
To find one solution, I added up (4)(5) + (3)(5)(3) + (3)(4)(4) to get 113. I tested this solution and it worked for the system of congruences.
How would you find all the other solutions to this? Would you use set builder notation?

Answer 1

Set-builder notation is just a compact way of describing a set. You can use set-builder notation to describe the set of solutions once you find out what that set is, but it won’t help you actually to find the solutions.

Proceed as in the video: $3\cdot4\cdot5=60$ is congruent to $0$ modulo $3,4$ and $5$, so adding or subtracting any integral multiple of $60$ won’t affect the value modulo $3,4$, or $5$. That is $60\equiv 0\pmod 3$, so $113+60n\equiv 2+0\cdot n\equiv 2\pmod 3$, so any number of the form $113+60n$ is still a solution to the first congruence. Similar calculations show that $113+60n\equiv 1\pmod 4$ and $113+60n\equiv 3\pmod 5$ for each integer $n$, so every number of the form $113+60n$ is a solution to the system of three congruences. It turns out that these are the only solutions, so the set of solutions is

$$\{113+60n:n\in\Bbb Z\}\;,$$

where as usual $\Bbb Z$ is the set of integers. Equivalently, it’s

$$\{n\in\Bbb Z:n\equiv 113\!\!\pmod{60}\}\;.$$

Note that in most contexts it’s customary to take $53$, obtained when $n=-1$, as a more or less standard representative of this set rather than $113$, so that one would more likely write

$$\{n\in\Bbb Z:n\equiv 53\!\!\pmod{60}\}\;.$$

Answer 2

Generally it is much easier to successively solve the system in pairs. For example:

${\rm mod}\ 5\!:\ 3\equiv x\iff x = \color{#0a0}{3+5i}$

$\smash[t]{{\rm mod}\ 4\!:\ 1\equiv x\equiv \color{#0a0}{3\!+\!5i}\equiv 3\!+\!i\iff i = -2\!+\!4j\iff x=\color{#0a0}{3\!+\!5}(\overbrace{-2\!+\!4j}^{\large\color{#0a0} i})=\,\color{#c00}{-7\!+\!20j}}$

$\smash[b]{{\rm mod}\ 3\!:\ 2\equiv x\equiv \color{#c00}{-7+20j}\equiv 2-j\iff j\equiv0\iff j=3k\iff x= \,\color{#c00}{-7+20}\underbrace{(3k)}_{\large\color{#c00}j}}$

Thus $\,x\,$ satisfies the system $\iff x\equiv \color{#c00}{-7}\equiv 53\pmod{60}$

Answer 3

The system of equations is

$$\begin{cases}x=\color{green}2\pmod 3\\ x=\color{green}1\pmod4\\ x=\color{green}3\pmod5\end{cases}$$

Now do as the proof here :

$$\begin{align}&N_1=20\implies x_1=N_1^{-1}\pmod3=\color{red}2\\ &N_2=15\implies x_2=N_2^{-1}\pmod4=\color{red}3\\ &N_3=12\implies x_3=N_3^{-1}\pmod5=\color{red}3\end{align}$$

and now we define

$$x:=20\cdot\color{green}2\cdot\color{red}2+15\cdot\color{green}1\cdot\color{red}3+12\cdot\color{green}3\cdot\color{red}3=233=53\pmod{3\cdot4\cdot5}=53\pmod{60}$$