Find all numbers $r$ for which the system of congruences is true

Question

Find all numbers $r$ for which the system of congruences \begin{align*} x &\equiv r \pmod{6}, \\ x &\equiv 9 \pmod{20}, \\ x &\equiv 4 \pmod{45} \end{align*}has a solution.

---

Guess and check won't work, thanks in advance for giving a solution!

Answer 1

From the second equation, since $x \equiv 9 \pmod{20}$, we know $x$ is odd. Then $r$ can be one of $1$, $3$, and $5$. From the third equation, $x \equiv 4 \pmod{45}$. We see that $x \equiv 1 \pmod{3}$ (since $x = 45y+4$, for some integer $y$). Then we see that $r$ can only be $1$ (since if $x \equiv 3 \mod{6}$, it will have remainder $0$ when divided by $3$ and if $x \equiv 5 \mod{6}$, it will have remainder $2$ when divided by $3$.

Answer 2

Hint: Prove first that a system of congruences $$\begin{cases}x\equiv r\mod a\\x\equiv s\mod b\end{cases}$$ has a solution if and only if $\; r\equiv s\mod\gcd(a,b).$

Answer 3

By the CRT, the constraint $x\equiv 9\pmod{20}$ is equivalent to the couple of constraints $x\equiv 4\pmod{5}$ and $x\equiv 1\pmod{4}$. In a similar way, the constraint $x\equiv 4\pmod{45}$ is equivalent to the couple of constraints $x\equiv 4\pmod{5}$ and $x\equiv 4\pmod{9}$. The last one implies $x\equiv 1\pmod{3}$ while $x\equiv 1\pmod{4}$ implies $x\equiv 1\pmod{2}$, hence the system has a solution iff $\color{red}{r\equiv 1\pmod{6}}$.