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)\]

.