2.3: Problem 17: Solve the congruence \(x^3 - 9x^2 + 23x - 15 \equiv 0 \pmod{503}\) by observing that \(503\) is a prime and that the polynomial factors into \((x-1)(x-3)(x-5)\).
Solution
We are given that the polynomial factors so into \((x-1)(x-3)(x-5)\)
$$
\begin{align*}
x^3 - 9x^2 + 23x - 15 &\equiv 0 \pmod{503} \\
(x-1)(x-3)(x-5) &\equiv 0 \pmod{503}
\end{align*}
$$
But since \(503\) is prime, then we must have
$$
\begin{align*}
(x-1) &\equiv 0 \pmod{503} \text{ or } \\
(x-3) &\equiv 0 \pmod{503} \text{ or } \\
(x-5) &\equiv 0 \pmod{503}
\end{align*}
$$
But this means that
$$
\begin{align*}
x &\equiv 1 \pmod{503} \text{ or } \\
x &\equiv 3 \pmod{503} \text{ or } \\
x &\equiv 5 \pmod{503}
\end{align*}
$$
So we have 3 solutions. (Side note: if \(n\) isn’t prime, then it’s not necessarily that if \(ab \equiv 0 \pmod{n}\) would imply that \(a \equiv 0\) or \(b \equiv 0\). Zero divisors do exist when \(n\) is not prime. As an example, observe that \(2 \cdot 3 \equiv 0 \pmod{6}\).