ABSTRACT
We discuss here polynomial congruences which lie at the heart of number theory. The main results below are due to Fermat, Lagrange, Euler, and Gauss.
Definition 33.1. Let f(x) ∈ Z[x] be a polynomial and p a prime. An integer c ∈ Z is called a root of f(x) mod p (or a solution to the congruence f(x) ≡ 0 (mod p)) if f(c) ≡ 0 (mod p); in other words if p|f(c). Let f ∈ Fp[x] be the polynomial obtained from f ∈ Z[x] by replacing the coefficients of f with their images in Fp. Then c is a root of f mod p if and only if the image c of c in Fp is a root of f . We denote by Np(f) the number of roots of f(x) mod p contained in
{0, 1, ..., p − 1}; equivalently Np(f) is the number of roots of f in Fp. If f, g are polynomials in Z[x] we write Np(f = g) for Np(f − g). If Zp(f) is the set of roots of f in Fp then of course Np(f) = |Zp(f)|.
