626 ANSWERS TO EXERCISES (Web server address) 4.6.2 1/2e- ; thus it
626 ANSWERS TO EXERCISES 4.6.2 1/2e- ; thus it will always be found immediately when pmod 4 = 3. If we choose t at random instead of increasing it sequentially, exercise 29 gives a rigorous proof that each t gives success at least about half of the time; but for practical purposes this random choice isn t needed. Another square-root method has been suggested by D. Shanks. When e > 1 it requires an auxiliary constant z (depending only on p) such that Z -~ E -1 (modulo p). The value z = nq modp will work for almost one half of all integers n; once z is known, the following algorithm requires no more probabilistic calculation: Sl. Set y + z, r + e, v t u(~+~)/ modp, w t uq modp. S2. If w = 1, stop; v is the answer. Otherwise find the smallest Ic such that wzk modp is equal to 1. If k = r, stop (there is no answer); otherwise set k-l (y, T, v, w) +-(y2 y k, vy2 - , wy2 -) and repeat step S2. 1 The validity of this algorithm follows from the invariant congruences uw E v2, 2r- -= -1 w2 -l = 1 (modulo p). On the average, step S2 will require about ie2 Multiplications mod p. Reference: Proc. Second Manitoba Conf. Numer. Math. (1972), 58-62. A related method was published by A. Tonelli, Gottinger Nachrichten (1891), 3444346. 16. (a) Substitute polynomials modulo p for integers, in the proof for n = 1. (b) The proof for n = 1 carries over to any finite field. (c) Since z = tk for some k, zpn = 2 in the field defined by f(z). Furthermore, the elements y that satisfy the equation YPrn = y in the field are closed under addition, and closed under multiplicatio;; so if xpm = 2, then [ (being a polynomial in z with integer coefficients) satisfies EP = 6. 17. If [ is a primitive root, each nonzero element is some power of c. Hence the order must be a divisor of 132 -1 = 23 .3 .7, and p(f) elements have order f. f P(f) f P(f) f co(f) f co(f) 1 1 3 2 7 6 21 12 2 1 6 2 14 6 42 12 4 2 12 4 28 12 84 24 8 4 24 8 56 24 168 48 18. (a) pp(pr(u,z)) . . . pp(p,(u,z)), by Gauss s lemma. For example, let u(x) = 6×3 -3X2 + 2x -1, v(x) = x3 -3~~ + 12x -36 = (x2 + 12)(x -3); then pp(36×2 + 12) = 3×2 f 1, pp(6x -3) = 2x -1. (This is a modern version of a fourteenth-century trick used for many years to help solve algebraic equations.) (b) Let pp(w(~~x)) = U,x + … + ?& = w(u~x)/c, where c is the content of w(unx) as a polynomial in x. Then w(x) = (c~/u~)s +. . . +c?i~s, hence cti, = u:; since ti,,, is a divisor of unr c is a multiple of 21F-l. 19. If U(X) = v(x)w(x) with deg(v)deg(w) 2 1, then U,X E v(z)w(x) (modulo p). By unique factorization modulo p, all but the leading coefficients of v and w are multiples of p, and p2 divides vow0 = 1~0.