Find all numbers r for which the system of congruences
x = r (mod 6)
x = 3 (mod 20)
x = 13 (mod 45)
has a solution.
+9519 Since \(x \equiv 3 \pmod{20}\), let x = 20k + 3 for some integer k.
\(20k + 3 \equiv 13\pmod{45}\\ 20k \equiv 10 \pmod{45}\\ 4k \equiv 2 \pmod{9}\\ 4k \equiv 20 \pmod{9}\\ k \equiv 5 \pmod 9\)
Then we can let k = 9n + 5 for some integer n. Substituting this into x = 20k + 3 gives x = 180n + 103.
Therefore, taking (mod 6), we have:
\(x \equiv 180n + 103\pmod 6\\ x \equiv 103 \pmod 6\\ x \equiv 1 \pmod 6\)
It turns out the system has a solution if and only if \(r \equiv 1 \pmod 6\), i.e., \(r = 6p + 1\) for some integer p.
