Unknown

3.4. Locating Integer Roots: Modular Arithmetic 95

take an odd value. Similarly, if t is given an odd value, then the value of
the polynomial is again odd. Thus, no substitution for t will give an even
value for the polynomial and the polynomial will always fail to vanish for
integer t. How can we extend this type of argument?
In the example, we made use of the fact that 0 is even. In fact, 0 is
the only integer which is divisible by every other integer, and in particular
by every prime. Accordingly, if a polynomial q(t) over Z has an integer
zero r, then q(r) E 0 (mod m) for each rn. On the one hand, we can
find candidates for integer zeros among the solutions of this congruence for
suitable values of m. On the other hand, if we can find an integer m for
which the congruence has no solution, then there can be no integer zero of
the polynomial.
In this section, we will be concerned with solving congruences of the
form q(t) E 0 (mod m). It turns out that we can do this by solving the
congruence when m is a prime power and piecing together the solutions for
prime powers to discover the solution for an arbitrary modulus.

Exercises

1. Consider the following congruence:

t2 - 9t - 36 E 0 (mod m)

(a) Show that the solutions of the congruence for m = 8 are the

same as the solutions of the congruence

t2 -t - 4 G 0 (mod 8).

Verify that the only solutions of the congruence modulo 8 are

t E 4 and t E 5. Write out all the integer solutions of the

congruence between 0 and 39 inclusive.

(b) Solve the congruence t2 - 9t - 36 E 0 (mod 5). Write out all the

integer solutions of the congruence between 0 and 39 inclusive.

(c) Show that every solution of the congruence t2 - 9t - 36 s 0

(mod 40) is a solution of the congruences in (a) and (b). Use

this fact to write out all the solutions of the congruence modulo

40 between 0 and 39 inclusive.

(d) Use the result of (c) to guess the zeros of the polynomial t2 -

9t - 36. Check your guesses.

2. Let q(t) be a polynomial over Z. Show that, if a E b (mod m), then
   q(a) E q(b) (mod m), for any posit*ive integer m.


3. Let q(t) be a polynomial over Z, and let m be a positive integer
   which is a product of prime powers pk. Argue that every solution of
   the congruence
   q(t) E 0 (mod m)