Let
\[p\]
be a prime and let \[P(x)\]
be a polynomial of degree \[k\]
. The equation \[P(x) \equiv 0 \; (mod \; p)\]
can have at most \[k\]
solutions.Modulus or not the equation
\[P(x)=0 \]
where \[P(x)\]
has degree k has at most \[k\]
solutions. Factorise \[P(x)\]
so \[P(x)=(x-x_1)(x-x_2)...(x-x_r)P_r(x)\]
where \[P_r(x)\]
is a polynomial of degree \[k-r\]
. This can be written \[mod \; p\]
by reducing all the \[x_i \; (mod \; p)\]
then if \[r=k\]
\[P_r(x)\]
is a constant and there are \[k\]
solutions.Proof
Suppose to the contrary that a polynomial congruence
\[P(x) \equiv 0 \; (mos \; p)\]
has incongruent solutions \[b_1, \; b_2,...., \; b_k, \; b_{l+1}\]
then we can write\[P(x) \equiv (x-b_1)(x-b_2)...(x-b_k)P_k(x) \; (mod \; p)\]
where
\[P_k(x)\]
has degree \[k-k=0\]
. Then \[P_k(x)\]
is a constant, say \[P_k(x)=c\]
.The leading term in
\[P(x)\]
will then be \[cx^k\]
.\[b_{k+1}\]
is a solution of \[P(x) \equiv 0 \; (mod \; p)\]
so \[P(b_{k+1}) \equiv c(b_{k+1}-b_1)(b_{k+1}-b_2)...(b_{k+1}-b_k) \equiv 0 \; (nod \; p)\]
.Then
\[p | c(b_{k+1}-b_1)(b_{k+1}-b_2)...(b_{k+1}-b_k)\]
.\[p\]
is prime so Euclid's Lemma implies \[p\]
divides one of the factors \[c, \; (b_{k+1}-b_1), \; (b_{k+1}-b_2),..., \; (b_{k+1}-b_k)\]
.
Neither of these is possible since \[0 \lt c, b_i \lt p\]
and the \[b_i\]
are incongruent modulo \[p\]
.Example:
\[P(x) =x^2-9x+20=(x-4)(x-5)\]
and \[p=3\]
.The solutions of
\[P(x)=0\]
are \[x=4, \; 5\]
and if we reduce \[P(x)\]
modulo 3 we get \[P(x) \equiv x^2+2=(x+2)(x+1)\]
and this equation has at most two solutions, which are \[x \equiv -2, \; -1 \; (mod \; ) \equiv 1, \; 2 \; (mod \; 3) \equiv 4, \; 5 \; (mod \; 3)\]
.