Skip to main content

Section 4.3 Polynomial Congruences

What about polynomial congruences? Certainly we must know something about those. We now consider the congruence

\begin{equation*} f(x) \equiv 0 \pmod{n} \end{equation*}

for \(f(x)\) a polynomial of degree \(n\) with integer coefficients.

We proceed by induction on the degree of \(f(x).\) If \(n = 0,\) then \(f(x) = a_0.\) Since \(a_0 \not\equiv 0\pmod{p},\) there are no solutions. If \(n = 1,\) then \(f(x) = a_1x+a_0;\) and we know from a previous theorem that the congruence

\begin{equation*} a_1x \equiv -a_0 \pmod{p} \end{equation*}

has exactly one solution modulo \(p,\) since \(\gcd(a_1, p) = 1.\)

Assume now that the theorem is true for all polynomials of degree \(n\) less than \(k,\) where \(k \geq 2.\) Suppose that \(f(x) = a_kx^k+...+a_0\) is a polynomial of degree \(k\) with \(k + 1\) mutually incongruent solutions modulo \(p,\) say \(w_1, w_2,..., w_{k+1}.\) We define the polynomial \(g(x)\) by

\begin{equation*} g(x) := f(x)-a_k(x-w_1)(x-w_2)...(x-w_k). \end{equation*}

Now \(g(x) \equiv f(x) \equiv 0 \pmod{p}\) if \(x = w_1, w_2,..., w_k.\) Furthermore, \(g(x)\) is a polynomial of degree less than \(k\) because the leading term of \(f(x)\) is cancelled by the \(a_kx^k\) term of the product on the right. Thus since the number of solutions of the congruence \(g(x) \equiv 0 \pmod{p}\) is larger than the degree of \(g(x),\) it follows from the induction hypothesis that

\begin{equation*} g(x) \equiv 0 \pmod{p} \end{equation*}

for each integer \(x.\) In particular,

\begin{equation*} g(w_{k+1}) \equiv 0 \pmod{p}. \end{equation*}

This gives

\begin{align*} 0 \amp \equiv g(w_{k+1}) \pmod{p}\\ \amp \equiv f(w_{k+1})-a_k(w_{k+1}-w_1)(w_{k+1}-w_2)...(w_{k+1}-w_k)\pmod{p} \\ \amp \equiv -a_k(w_{k+1}-w_1)(w_{k+1}-w_2)...(w_{k+1}-w_k)\pmod{p} \end{align*}

Thus \(p\vert a_k(w_{k+1}-w_1)(w_{k+1}-w_2)...(w_{k+1}-w_k).\) If \(p\vert a_k\) then the problem reduces to the assumed case. If \(p \nmid a_k\) then since the \(w_i\) are mutually incongruent, the difference between any two \(w_i\)'s is not divisible by \(p,\) a contradiction.

Thus the congruence \(f(x) \equiv 0 \pmod{p}\) has at most \(k\) mutually incongruent solutions, and the theorem is proved.