2.3: Problem 02: Find all integers that satisfy simultaneously \(x \equiv 2 \pmod{3}\), \(x \equiv 3 \pmod{5}\) and \(x \equiv 5 \pmod{2}\).
Solution
The last congruence simplifies to \(x \equiv 5 \pmod{2}\). We want to solve the system of congruences
$$
\begin{align*}
x \equiv 2 \pmod{3} \\
x \equiv 3 \pmod{5} \\
x \equiv 1 \pmod{2}
\end{align*}
$$
Since \(3\), \(5\), and \(2\) are pairwise coprime, CRT guarantees a unique solution modulo \(3 \cdot 5 \cdot 2 = 30\). Using the first congruence we know that \(x = 3k + 2\) for some integer \(k\). We can plug this into the second congruence to see that
$$
\begin{align*}
x &\equiv 3 \pmod{5} \\
3k + 2 &\equiv 3 \pmod{5} \\
3k &\equiv 1 \pmod{5} \\
2 \cdot 3k &\equiv 2 \cdot 1 \pmod{5} \quad \text{($2$ is the inverse of $3$ modulo $5$)} \\
k &\equiv 2 \pmod{5}
\end{align*}
$$
From this we get that \(k = 5m + 2\) for some integer \(m\). Then
$$
\begin{align*}
x = 3k + 2 = 3(5m + 2) + 2 = 15m + 8
\end{align*}
$$
So now we have a solution that satisfies congruence \(1\) and \(2\). Next, we solve the system
$$
\begin{align*}
x &\equiv 8 \pmod{15} \\
x &\equiv 1 \pmod{2}
\end{align*}
$$
The first congruence implies that \(x = 15s + 8\). We plug this into the second congruence to get
$$
\begin{align*}
15s + 8 &\equiv 1 \pmod{2} \\
15s &\equiv -7 \pmod{2} \\
s &\equiv 1 \pmod{2} \\
\end{align*}
$$
This implies that \(s\) is odd of the form \(s = 2r + 1\). We plug this back into
$$
\begin{align*}
x = 15(2r+1) + 8 = 30r + 15 + 8 = 30r + 23
\end{align*}
$$
This implies that
$$
\begin{align*}
x \equiv 23 \pmod{30}
\end{align*}
$$
Every integer of the form \(x = 30r + s\) is a solution to the original system of congruences
$$
\begin{align*}
x \equiv 2 \pmod{3} \\
x \equiv 3 \pmod{5} \\
x \equiv 1 \pmod{2}
\end{align*}
$$
This again follows from the Chinese Remainder Theorem since \(5\), \(3\) and \(2\) are pairwise coprime.
References