Simple web server - 4.6.2 ANSWERS TO EXERCISES 629 smallest prime that
4.6.2 ANSWERS TO EXERCISES 629 smallest prime that is not unlucky is at most O(n log Nn), if n = deg(u) and N bounds the coefficients of U(X).] 24. Multiply a manic polynomial with rational coefficients by a suitable nonzero integer, to get a primitive polynomial over the integers. Factor this polynomial over the integers, and then convert the factors back to manic. (No factorizations are lost in this way; see exercise 4.6.1-8.) 25. Consideration of the constant term shows there are no factors of degree 1, so if the polynomial is reducible, it must have one factor of degree 2 and one of degree 3. Modulo 2 the factors are ~(5 f 1) (x2 + x + 1); this is not much help. Modulo 3 the factors are (5 + 2)2(~3 + 2x f 2). Modulo 5 they are (x2 + x + 1)(z3 + 4x + 2). So we see that the answer is (x2 + x + 1)(x3 -x $2). 26. Begin with D + (0 . . . Ol), representing the set (0). Then for 1 5 j 5 r, set D + D V (D 7 dj), where V denotes logical or and D 7 d denotes D shifted left d bit positions. (Actually we need only work with a bit vector of length [(n + 1)/2], since n -m is in the set iff m is.) 27. Exercise 4 says that a random polynomial of degree n is irreducible modulo p with rather low probability, about l/n. But the Chinese remainder theorem implies that a random manic polynomial of degree n over the integers will be reducible with respect to each of Ic distinct primes with probability about (1 - l/n)k, and this approaches zero as k + co. Hence almost all polynomials over the integers are irreducible with respect to infinitely many primes; and almost all primitive polynomials over the integers are irreducible. [Another proof has been given by W. S. Brown, AMM 70 (1963), 965-969. See also the generalization cited in the answer to exercise 36.1 28. Cf. exercise 4; the probability is the coefficient of zn in (l+al,z/p)(l+a2,z2/p2) X (lfaa,z3/p3). . , which has the limiting value g(z) = (1 + z)(l + $z2)(1 $ 4~ ). . . . For 1 5 n 5 10 the answers are 1, 3, 8, A, $&, a, #, #&, H, $$i#. [Let f(y) = ln(1 + y) -y = O(y2). We have g(z) = exp(& 1 znln + En2 1 W/n)) = h(z)l(l -Zh and it can be shown that the limiting probability is h(1) = exp(xn,r f(l/n)) = e–1 M .56146 as n -+ co; cf. D. H. Lehmer, Acta Arith. 21 (1972) 3791388. Indeed, N. G. de Bruijn has established the asymptotic formula lim,,, anp = eer +e- /n+ O(nb2 log n).] 29. Let ql(z) and q2(x) be any two of the irreducible divisors of g(x). By the Chinese remainder theorem (exercise 3), choosing a random polynomial t(x) of degree < 2d is equivalent to choosing two random polynomials ti(z) and tz(x) of degrees < d, where ti(x) = t(x)modqi(x). The gcd will be a proper factor if ti(~)(~~-l)/~ modqi(x) = 1 and tz(~)(~~- )/~ modqr(x) # 1, or vice versa, and this condition holds for exactly 2((pd -1)/2)((# + 1)/2) = (p2d - 1)/2 choices of ti(x) and tz(x). Notes: We are considering here only the behavior with respect to two irreducible factors, but the true behavior is probably much better. Suppose that each irreducible factor q%(x) has probability f of dividing t(~)(~~- )/~ -1 for each t(x), independent of the behavior for other qj(x) and t(x); and assume that g(x) has r irreducible factors in all. Then if we encode each qi(x) by a sequence of O s and l s according as qi(x) does or doesn t divide t(x)(pd- )/2 -1 for the successive t s tried, we obtain a random binary