3.4. Locating Integer Roots: Modular Arithmetic 97
(c) Let c = clal + c2a2 + c3a3 + .-. + c,a,.
- For which positive values of the integer n is ns - n2 not divisible by
504? - (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.
- 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.
- 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.