528 ANSWERS TO (Web hosting asp) EXERCISES 3.2.2 there must exist
528 ANSWERS TO EXERCISES 3.2.2 there must exist polynomials a(z) and b(z) such that pefl(u(z) + pa(z)) = f(z)b(z). Since f(0) = 1, this implies that b(z) is a multiple of pef (by Gauss s Lemma 4.6.1G); hence V(Z) E 0 (modulo f(z) and p), a contradiction. (b) If zx - 1 = f(z)u(z) $ p v(z), then G(z) = 4Mz -1) + ~ Wlf(z)(z~ -1); hence An+i E A, (modulo p ) for large n. Conversely, if (An) has the latter property then G(z) = u(z) + v(z)/(l -z ) + peH(z), f or some polynomials u(z) and V(Z), and some power series H(z), all with integer coefficients. This implies the identity 1-zx = u(z)f(z)(l -z )+~(z)f(z)+p~H(z)f(z)(l-zzX); and H(z)f(z)(l -zx) is a polynomial since the other terms of the equation are polynomials. (c) It suffices to prove that X(p ) # X(p + ) implies that X(p + ) = pX(pe) # X(p +*). Applying (a) and (b), we know that X(p +*) # pX(pe), and that X(pefl) is a divisor of pX(pe) but not of X(p ). Hence if X(p ) = pfq, where qmodp # 0, then X(p + ) must be p f+ d where d is a divisor of 4. But now Xn+rf+l E X, (modulo p ); hence p + d is a multiple of pfq, hence d = q. [Note: The hypothesis p > 2 is necessary; for example, let al = 4, us = -1, k = 2; then (An) = 1, 4, 15, 56, 209, 780, . . ; X(2) = 2, X(4) = 4, X(8) = 4.1 (d) g(z) = Xo + (XI -alXo)z + . . . +(x&-l -UlXk-2 -U2Xk-3 -. . . -uk-lXO)Zk–l. (e) The derivation in (b) can be generalized to the case G(z) = g(z)/f(z); then the assumption of period length X implies that g(z)(l -z ) E 0 (modulo f(z) and p ); we treated only the special case g(z) = 1 above. But both sides of this congruence can be multiplied by Hensel s b(z), and we obtain 1 - zx = 0 (modulo f(z) and p ). Note: A more elementary proof of the result in (c) can be given without using generating functions, using methods analogous to those in the answer to exercise 8: If Alfn. = A, + p B,, for n = r, r + 1,. . . , r + k -1 and some integers B,, then this same relation holds for dl n 2 r if we define &+k, &+k+r, . . . by the given recurrence relation. Since the resulting sequence of B s is some linear combination of shifts of the sequence of A s, we will have &+, E B, (modulo p ) for all large enough values of n. Now X(p +l) must be some multiple of X = X(pe); for all large enough n we have An+jx = An+p’(Bn+Bn+x +Bn+zx+. . .+B,+(j-1)~) E A,+jpeBn (modulo p ) forj=1,2,3 ,… . No k consecutive B s are multiples of p; hence X(p + ) = pX(pe) # X(pe+*) follows immediately when e 2 2. We still must prove that X(p +*) # pX(p ) when p is odd and e = 1; here we let Bx+, = B,, +pC,, and observe that C&+X E C, (modulo p) when n is large enough. Then A,+, E A, +p2(Bn + (g)C-) (modulo p ), and the proof is readily completed. For the history of this problem, see Morgan Ward, Trans. Amer. Math. Sot. 35 (1933), 600-628; see also D. W. Robinson, AMA4 73 (1966), 619-621. 12. The period length mod 2 can be at most 4; and the period length mod Zefl is at most twice the maximum length mod 2 , by the considerations of the previous exercise. So the maximum conceivable period length is 2ef1; this is achievable, for example, in the trivial case a = 0, b = c = 1. 13, 14. Clearly ,&+A = Z,, so X is certainly a divisor of X. Let the least common multiple of X and X1 be Xi, and define Xi similarly. X, + Y, = 2, ZE Zn+x; EE XI + yn+x;, so Xi is a multiple of X2. Similarly, Xi is a multiple of X1. This yields the desired result. (The result is best possible in the sense that sequences for which X = X0 can be constructed, as well as sequences for which X = X.)