The theory of numbers, by Robert D. Carmichael ...

42

THEORY OF NUMBERS

But, from algebra, f(x)-f(a) is divisible by x-a. Let (x-a)"
be the highest power of x-a contained in f(x)-f(a). Then
we may write
f(x) -f(a) = (x- a)f i (x), (2)
where fi(x) is evidently a polynomial with integral coefficients.
Hence we have
f(x) - (x - a)f (x) mod p. (3)
We shall say that a occurs a times as a solution of (i); or that
the congruence has a solutions each equal to a.
Now suppose that congruence (I) has a root b such that
bta mod p. Then from (3) we have
f(b) (b - a) fj(b) mod p.
But f(b) -o mod p, (b-a)-Sf mnod p.
Hence, since p is a prime number, we must have
fl(b) =o mod p.
By an argument similar to that just used above, we may
show that f (x) -f (b) may be written in the form
fi(x) -f,(b) = (x - b)J2(),
where 3 is some positive integer. Then we have
f(x) (x-a)a(- b) OJ(x) mod p.
Now this process can be continued until either all the
solutions of (I) are exhausted or the second member is a product of linear factors multiplied by the integer ao. In the former case there will be fewer than n solutions of (i), so that
our theorem is true for this case. In the other case we have
f(x) -ao(x-a)a(x-b) )... (x-l)x mod p.
We have now n solutions of (i): a counted a times, b counted
6 times,..., I counted X times; a+-+.. X=n.