Web design online - 4.3.2 ANSWERS TO EXERCISES 585 3. u =
4.3.2 ANSWERS TO EXERCISES 585 3. u = uz (modulo m,) implies that u E LL% (modulo gcd(mi, mj)), so the condition uz G u3 (modulo gcd(m,, m3)) must surely hold if there is a solution. Furthermore if u F w (modulo m3) for all j, then u - u is a multiple of lcm(mi, . . , m,) = m; hence there is at most one solution. The proof can now be completed in a nonconstructive manner by counting the number of different r-tuples (~1,. . . , u?) satisfying the conditions 0 2 u3 < m3 and 2~~= uj (modulo gcd(m,, m3)). If this number is m, there must be a solution since (Umodml,…, ~modm,) takes on m distinct values as u goes from a to a f m. Assume that ~1,. , ~~-1 have been chosen satisfying the given conditions; we must now pick u7 = uj (modulo gcd(mj, m,)) for 1 5 j < r, and by the generalized Chinese remainder theorem for r -1 elements there are m/lcm(gcd(ml, m), . , gcd(m,-1, m,)) = m,/gcd(lcm(m1,. . , m-l), m,) = lcm(mi, , m,)/lcm(mr, . . . , m7-i) ways to do this. [This proof is based on identities (lo), (11) (12) and (14) of Section 4.5.2.1 A constructive proof [A. S. F raenkel, Proc. Amer. Math. Sot. 14 (1963), 790-7911 generalizing (24) can be given as follows. Let M3 = lcm(mi, . , mj); we wish to find u = v,M,-, + . . . + v2M1 + vi, where 0 5 oJ < M3/Mj–1. Assume that vi, . . , v3-i have already been determined; then we must solve the congruence w3M3–1 +v3–1MJ-2 +..+wi F 1~~ (modulo m3). Here ~~~-1 M3-~ + . . . + wi = 1~~ G U? (modulo gcd(mi, m3)) for i < j by hypothesis, so c = 1~~-( j-r Mj+-2 + . + ~1) is a multiple of lcm(gcd(mr, m,), , gcd(m,-1, m3)) = gcd(Mj-1, mj) = d,. We therefore must solve v.,M~-~ = c (modulo mj). By Euclid s algorithm there is a number c3 such that c3M3-l G d, (modulo m,); hence we may take wj = (cj c)/dJ mod (m3/d3). Note that, as in the nonconstructive proof, we have m,ld, = M3/Mj-1. 4. (After m4 = 91 = 7.13, we have used up all products of two or more odd primes that can be less than 100, so ms, must all be prime.) m7 = 79, ma = 73, mg = 71, ml0 = 67, ml1 = 61, ml2 = 59, ml3 = 53, ml4 = 47, mis = 43, ml6 = 41, ml7 = 37, ml8 = 31, ml9 = 29, mss = 23, m21 = 17, and then we are stuck (mzz = 1 does no good). 5. No. The obvious upper bound, 34527211 . . = J-J pt % lOOl, podd p prime is attained if we choose ml = 34, m2 = 52, etc. (It is more difficult, however, to maximize ml . . . m7 when r is fixed, or to maximize ml +. . +m, as we would attempt to do when using moduli 2mj -1.)