Exercise 2.7.6 (Theorem 2.26 is false for composite moduli)

Proof. By Theorem 2.26, the congruence $f(x)\equiv 0(\mathit{mod}p)$ if degree $n$ has at most $n$ solutions. To prove that this proposition is false if we replace “mod p” by “mod m”, it is sufficient to give a counterexample.

In Exercise 2.6.1, we proved that the congruence $x^2+x+7\equiv 0(\mathit{mod}27)$, of degree $2$, has three solutions $4,13,22$ modulo $27$.

In Exercise 2.3.13, we showed that $x^3+2x-3\equiv 0(\mathit{mod}45)$, of degree $3$, has $6$ solutions $1,6,11,28,33,38$ modulo $45$.

This is sufficient to prove that Theorem 2.26 is false for composite moduli. □