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?
Best Answer
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}\}\;.$$