2.3: Problem 14: Solve the congruences:
$$
\begin{align*}
x^3 + 2x - 3 &\equiv 0 \pmod{9}; \\
x^3 + 2x - 3 &\equiv 0 \pmod{5}; \\
x^3 + 2x - 3 &\equiv 0 \pmod{45};
\end{align*}
$$
Solution
For the first congruence, we can try \(x = 0,1,2,\cdots,8\) to see that
$$
\begin{align*}
(0)^3 + 2(0) - 3 &\equiv -3 \equiv 6 \pmod{9} \\
(1)^3 + 2(1) - 3 &\equiv 0 \pmod{9} \\
(2)^3 + 2(2) - 3 &\equiv 9 \equiv 0 \pmod{9} \\
(3)^3 + 2(3) - 3 &\equiv 3 \pmod{9} \\
(4)^3 + 2(4) - 3 &\equiv 6 \pmod{9} \\
(5)^3 + 2(5) - 3 &\equiv 132 \equiv 6 \pmod{9} \\
(6)^3 + 2(6) - 3 &\equiv 225 \equiv 0 \pmod{9} \\
(7)^3 + 2(7) - 3 &\equiv 354 \equiv 3 \pmod{9} \\
(8)^3 + 2(8) - 3 &\equiv 525 \equiv 3 \pmod{9}
\end{align*}
$$
So the solutions are
$$
\begin{align*}
x \equiv 0,2,6 \pmod{9} \\
\end{align*}
$$
Next, we can try \(x = 0,1,2,3,4\) for the second congruence
$$
\begin{align*}
(0)^3 + 2(0) - 3 &\equiv -3 \equiv 2 \pmod{5} \\
(1)^3 + 2(1) - 3 &\equiv 0 \pmod{5} \\
(2)^3 + 2(2) - 3 &\equiv 9 \equiv 4 \pmod{5} \\
(3)^3 + 2(3) - 3 &\equiv 30 \equiv 0 \pmod{5} \\
(4)^3 + 2(4) - 3 &\equiv 69 \equiv 4 \pmod{5}
\end{align*}
$$
So the solutions are
$$
\begin{align*}
x \equiv 1,3 \pmod{5} \\
\end{align*}
$$
Now, recall that CRT says since \((5,9)=1\) and if we have a solution module \(9\) and a solution module \(5\), then there is a unique solution module \(5 \cdot 9 = 45\). So we can try each pair from \(\{1,2,6\} \times \{1,3\}\) to get a new solution module \(45\). First, we have
$$
\begin{align*}
x \equiv 1 \pmod{9} \\
x \equiv 1 \pmod{5}
\end{align*}
$$
Then, by CRT, \(1\) is a solution module \(45\). Next
$$
\begin{align*}
x \equiv 1 \pmod{9} \\
x \equiv 3 \pmod{5}
\end{align*}
$$
If we try values for \(x\), we will see that \(x = 28\) is a solution. If we want to solve this, then observe that from the first equation \(x = 9k + 1\). Now we can plugin in the second congruence to see that
$$
\begin{align*}
9k + 1 &\equiv 3 \pmod{5} \\
9k &\equiv 2 \pmod{5} \\
4k &\equiv 2 \pmod{5} \\
4\cdot 4k &\equiv 4 \cdot 2 \pmod{5} \\
k &\equiv 8 \pmod{5} \\
k &\equiv 3 \pmod{5}
\end{align*}
$$
We can plug this back into
$$
\begin{align*}
x &= 9k + 1 \\
x &= 9(5m + 3) + 1 \\
x &= 45m + 27 + 1 \\
x &= 45m + 28
\end{align*}
$$
This implies that \(x \equiv 28 \pmod{45}\) so \(28\) is a solution. Next, we can repeat the same process to find solutions for the pairs
$$
\begin{align*}
x \equiv 2 \pmod{9} \\
x \equiv 1 \pmod{5}
\end{align*}
$$
,
$$
\begin{align*}
x \equiv 2 \pmod{9} \\
x \equiv 3 \pmod{5}
\end{align*}
$$
,
$$
\begin{align*}
x \equiv 6 \pmod{9} \\
x \equiv 1 \pmod{5}
\end{align*}
$$
and finally
$$
\begin{align*}
x \equiv 6 \pmod{9} \\
x \equiv 3 \pmod{5}
\end{align*}
$$
\(\cdots\)
References