Medical web site - 3.2.1.2 ANSWERS TO EXERCISES 523 6. (Cf. previous
3.2.1.2 ANSWERS TO EXERCISES 523 6. (Cf. previous exercise.) a 3 1 (modulo 3.7 . 11 . 13.37) implies that the solutions are a = 1 f llllllk, for 0 5 k 5 8. 7. Using the notation of the proof of Lemma Q, p is the smallest value such that X P+x = X,; so it is the smallest value such that Y,+x = Yp and .Zcl+x = 2,. This shows that p = max(pi, . . . , pt). The highest achievable p is max(ei, . . . , et), but nobody really wants to achieve it. 8. We have a2 = 1 (modulo 
; so a4 G 1 (modulo 16), us = 1 (modulo 32), etc. If a mod 4 = 3, then a-1 is twice an odd number; so (aze- -1)/2 = 0 (modulo 2 + /2), and this yields the desired result. 9. Substitute for X, in terms of Y, and simplify. If Xc mod 4 = 3, the formulas of the exercise do not apply; but they do apply to the sequence 2, = (-Xn) mod 2e, which has essentially the same behavior. 10. Only m = 1, 2, 4, pe, and 2pe, for odd primes p. In all other cases, the result of Theorem B is an improvement over Euler s theorem (exercise 1.2.4-28). 11. (a) Either z+l or z-l (not both) will be a multiple of 4, so ~71 = 92f, where q is odd and f is greater than 1. (b) In the given circumstances, f < e and so e 2 3. We have -& = 1 (modulo 2f) and fz $1 (modulo af+ ) and f > 1. Hence by applying Lemma P, we find that (f~) ~- - $ 1 (modulo 27, while z2e–f = (*z) -~ E 1 (modulo 27. So the order is a divisor of 2e- , but not a divisor of Zemf- . (c) 1 has order 1; 2e -1 has order 2; the maximum period when e 2 3 is therefore 2e-2, and for e 2 4 it is necessary to have f = 2, that is, z = 4 f 1 (modulo . 12. If k is a proper divisor of p -1 and if uk G 1 (modulo p), then by Lemma P we have ukpe- = 1 (modulo p ). Similarly, if up- = 1 (modulo p ), we find that u(P-l)P -* -1 (modulo p ). So in these cases a is not primitive. Conversely, if up- $ 1 (zodulo p ), Theorem 1.2.4F and Lemma P tell us that u(~- )~ -~ $ 1 (modulo p ), but u(~- )~~- G 1 (modulo p ). So the order is a divisor of (p -l)pe- but not of (p -l)pep2; it therefore has the form kpe- , where k divides p -1. But if a is primitive modulo p, the congruence a kpe- = uk = 1 (modulo p) implies that k=p-1. 13. Let X be the order of a modulo p. By Theorem 1.2.4F, X is a divisor of p -1. If X < p -1, then (p -1)/X has a prime factor, q. 14. Let 0 < k < p. If up- = 1 (modulo p2), then (a + kp)*- E up- + (p -1)X uP-2kp (modulo p2); and this is $ 1, since (p -l)uPp2k is not a multiple of p. By exercise 12, a + kp is primitive modulo pe. 15. (a) If Xi =pi ...p;t,X2 =pf ...pft, let ~1 =pyl...py,~,a =p: ...pft, where g3 = e3 and hi = 0, if ej