asserts that the congruence a1x=-a0(mod p) has a unique solution modulo p. Thus, the theorem holds for n = 1.
Now assume inductively that the theorem is true for polynomials of degree k — 1, and consider the case in which f(x) has degree k. Either the congruence f(x)= 0(mod p) has no solutions (and we are finished), or it has at least one solution, call it a. If f(x) is divided by x —a, the result is