Unknown

3.4. Locating Integer Roots: Modular Arithmetic 97

(c) Let c = clal + c2a2 + c3a3 + .-. + c,a,.

8. For which positive values of the integer n is ns - n2 not divisible by
   504?


9. (a) Solve th e f o II owing congruence modulo 4 and modulo 9:

8t2 -7t+9=0.

(b) Argue that, by the Chinese Remainder Theorem, there should

be two incongruent solutions of the congruence in (a) modulo

36.

(c) Find the solutions of the congruence modulo 36.

10. How many positive integers less than 48 satisfy each of the systems
    of congruences:

(a) x z 5 (mod S), x E 4 (mod 8)

(b) y E 5 (mod 6), y E 3 (mod 8)

(c) z E 3 (mod 6), z E 5 (mod 8)?

Use this exercise to argue that in general the Chinese Remainder

Theorem is false if the condition that the factors of m are pairwise

coprime is dropped.

11. Solve the congruence t2 + 2 s 0 (mod 243) by following these steps:

(a) Noting that 243 E 35, argue that any solution of the congruence

satisfies t2 + 2 E 0 (mod 3).

(b) Verify that t2 + 2 E 0 (mod 3) is satisfied by t E 1 (mod 3).

(c) We now turn to the congruence t2 + 2 z 0 (mod 9). Show that

if t = 1 + 3u is a solution to this congruence, then

which implies that 1 + 2u z 0 (mod 3). Thus, 21 = 1 + 3v, and

t=4+9v.

(d) Show that, if t = 4 + 9v and t2 + 2 z 0 (mod 27), then

18 + 72v + 81v2 z 0 (mod 27).

Reduce this to the equivalent congruence 1 + v E 0 (mod 3).

Thus, t = 22 + 27~.

(e) Continue the process to obtain, in turn, a solution of

t2+2=o

modulo 81 and modulo 243. Check your answer.