2.3: Problem 17: Solve the congruence \(x^3 - 9x^2 + 23x - 15 \equiv 0 \pmod{143}\).
Solution
The polynomial factors just like in problem \(16\) but \(143\) is not prime here.
$$
\begin{align*}
x^3 - 9x^2 + 23x - 15 &\equiv 0 \pmod{143} \\
(x-1)(x-3)(x-5) &\equiv 0 \pmod{11 \cdot 13}
\end{align*}
$$
\(11\) and \(13\) are coprime. Then by CRT, if we have a solution to the system
$$
\begin{align*}
(x-1)(x-3)(x-5) &\equiv 0 \pmod{11} \\
(x-1)(x-3)(x-5) &\equiv 0 \pmod{13}
\end{align*}
$$
Then, we must have a unique solution modulo \(143\). Since \(11\) is prime, then we must have that
$$
\begin{align*}
x - 1 &\equiv 0 \pmod{11} \text{ or } \\
x - 3 &\equiv 0 \pmod{11} \text{ or } \\
x - 5 &\equiv 0 \pmod{11}
\end{align*}
$$
Therefore,
$$
\begin{align*}
x &\equiv 1,3,5 \pmod{11}
\end{align*}
$$
Similarly, \(13\) is also prime. Therefore,
$$
\begin{align*}
x &\equiv 1,3,5 \pmod{11}
\end{align*}
$$
Now, we know that CRT guarantees a unique solution modulo \(143\) for every pair of values we have. The following will list every unique solution for each pair.
- When \(x \equiv 1 \pmod{11}\) and \(x \equiv 1 \pmod{13}\), clearly the unique solution is
$$ \begin{align*} x \equiv 1 \pmod{143} \end{align*} $$
- When \(x \equiv 1 \pmod{11}\) and \(x \equiv 3 \pmod{13}\), then we can try substituting equation 1 into the second to see that
$$ \begin{align*} 11k + 1 &\equiv 3 \pmod{13} \\ 11k &\equiv 2 \pmod{13} \\ 6 \cdot 11k &\equiv 6 \cdot 2 \pmod{13} \\ k &\equiv 12 \pmod{13} \end{align*} $$Now, we plug this back into \(x = 11k + 1 = 11(13m + 2) + 1 = 143m + 133\). Therefore$$ \begin{align*} x \equiv 133 \pmod{143} \end{align*} $$
- When \(x \equiv 1 \pmod{11}\) and \(x \equiv 5 \pmod{13}\), then we can try substituting equation 1 into the second to see that
$$ \begin{align*} 11k + 1 &\equiv 5 \pmod{13} \\ 11k &\equiv 4 \pmod{13} \\ 6 \cdot 11k &\equiv 6 \cdot 4 \pmod{13} \\ k &\equiv 11 \pmod{13} \end{align*} $$Now, we plug this back into \(x = 11k + 1 = 11(13m + 11) + 1 = 143m + 122\). Therefore$$ \begin{align*} x \equiv 122 \pmod{143} \end{align*} $$
- When \(x \equiv 3 \pmod{11}\) and \(x \equiv 1 \pmod{13}\), TODO ...
- When \(x \equiv 3 \pmod{11}\) and \(x \equiv 3 \pmod{13}\), the unique solution is
$$ \begin{align*} x \equiv 3 \pmod{143} \end{align*} $$
- When \(x \equiv 3 \pmod{11}\) and \(x \equiv 5 \pmod{13}\), then we can try substituting equation 1 into the second to see that
$$ \begin{align*} 11k + 3 &\equiv 5 \pmod{13} \\ 11k &\equiv 2 \pmod{13} \\ 6 \cdot 11k &\equiv 6 \cdot 2 \pmod{13} \\ k &\equiv 12 \pmod{13} \end{align*} $$Now, we plug this back into \(x = 12k + 3 = 12(13m + 12) + 3 = 143m + 135\). Therefore$$ \begin{align*} x \equiv 135 \pmod{143} \end{align*} $$
- When \(x \equiv 5 \pmod{11}\) and \(x \equiv 1 \pmod{13}\), TODO ...
- When \(x \equiv 5 \pmod{11}\) and \(x \equiv 3 \pmod{13}\), TODO ...
- When \(x \equiv 5 \pmod{11}\) and \(x \equiv 5 \pmod{13}\), the unique solution is \(x \equiv 5 \pmod{143}\).