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

ELEMENTARY PROPERTIES OF CONGRUENCES

43

Now let q7 bh any solution of (i). Then
f(q) = ao(r —a) (r1 —b)... (r-/1)X _o mod p.
Since p is prime it follows now that some one of the factors
7)-a, n-b,..., r-l1 is divisible by p. Hence 7q coincides
with one of the solutions a, b, c,..., 1. That is, (I) can
have only the n solutions already found.
This completes the proof of the theorem.
EXERCISES
I. Construct a congruence of the form
aoxn-alxn —1-... +an=o mod m, aoo mod m,
having more than n solutions and thus show that the limitation to a prime modulus in the theorem of this section is essential.
2. Prove that
x6-I3(x-I)(x-2)(x-3)(X-4)(x-5)(x-6) mod 7
for every integer x.
3. How many solutions has the congruence XS-m mod ii? the congruence
X5-2 mod II?
~ 22. LINEAR CONGRUENCES
From the theorem of the preceding section it follows that
the congruence
axm=c mod p, ao mod p,
where p is a prime number, has not more than one solution.
In this section we shall prove that it always has a solution.
More generally, we shall consider the congruence
ax =c mod m
where m is any integer. The discussion will be broken up
into parts for convenience in the proofs.
I. The congruence

ax i mod m,

(I)