624 ANSWERS TO EXERCISES 4.6.2 4. By unique (Database web hosting)
624 ANSWERS TO EXERCISES 4.6.2 4. By unique factorization, we have (1 -pz)- = fl,>, (1 -z~)-~~P; after taking logarithms, this can be rewritten &l G,(z?/J = &rl akpzkjlj = ln(l/(l -PZ)). The stated identity now yields the answer G*(z) = xnZI p(m)m- ln(l/(l -pzm)), from which we obtain anp = zd,n p(n/d)n- pd; thus lim,,, anp/pn = l/n. TO prove the stated identity, note that c n,j 2 1 ~(nMz W .F = Cm2 1 dzm)m-t C,,, AnI = g(z). 5. Let anp7 be the number of manic polynomials of degree n modulo p having exactly r irreducible factors. Then &(z, w) = zn,r20 anp7znwr = exp( xk21 G,(zk)wk/k), where G, is the generating function in exercise 4; cf. Eq. 1.2.9-34. We have Cn>O Anpzn = d&(zlp, w)ldw lw=l = (xk>l Gp(zklpk))exp(ln(ll(l -Z))> - = (Cnzl 141/U -p - z ))cp(n)lnMl -4 hence A,, = H, + 1/2p + O(p- ) for n 2 2. The average value of 2 is the coefficient of zn in &(z/p, 2), namely n + l-j-(n -1)/p + O(p- ). (The variance is of order n3, however: set w = 4.) 6. For 0 2 s < p, x -s is a factor of xp -5 (modulo p) by Fermat s theorem. So xp -2 is a multiple of lcm(s -0, x -1,. . . , z -(p -1)) = xp. [Note: Therefore the Stirling numbers [E] are multiples of p except when Ic = 1, Ic = p. Equation 1.2.6-41 shows that the same statement is valid for Stirling numbers {E} of the other kind.] 7. The factors on the right are relatively prime, and each is a divisor of U(Z), so their product divides U(X). On the other hand, U(X) divides 4×1 -4x) = no+