suppose you have a polynomial $P(x) = a_0+a_1x+...+a_kx^k$. How can you prove that at most $k$ numbers satisfy $P(x) \equiv 1 \mod n$ ? To me this looks like the fundamental theorem of algebra, however, in modular arithmetic. Yet, I don't see why the theorem would apply here as well.
Thanks in advance.
This is only true if $n$ is a prime.
If you take $n = 15$, for instance, the polynomial $x^{2} - 1$ has the four roots $1, 4, 11, 14$ modulo $n$.
When $n = p$ is a prime, you exploit the fact that $\mathbb{Z} / p \mathbb{Z}$ is a field, and recycle the usual proof.
I wouldn't call it the fundamental theorem of algebra, though, as that refers to the fact that a non-constant polynomial splits in linear factors in $\mathbb{C}[x]$.
