4.6.2 ANSWERS TO EXERCISES 623 have c&-l + (Web site counters)
4.6.2 ANSWERS TO EXERCISES 623 have c&-l + e, = d, + en+1 > d, + e,-1. Therefore deg(pu -qw) = deg(c) + dnpl; but we have assumed that deg(pu -qv) < d,-2 = d,-1 + e, -e,-1, so deg(c) < en -e,-1 and deg(d) < 0, a contradiction. [This result is essentially due to L. Kronecker, Monatsberichte Kiinigl. PreuD. Akxd. Wiss. (Berlin: 1881), 535-600. It implies the following theorem: Let U(X) and V(Z) be relatively prime polynomials over a field and let d 2 deg(v) < deg(u). If q(z) is a polynomial of least degree such that there exist polynomials p(z) and r(2) with p(z)u(z) -q(z)v(s) = T(Z) and deg(r) = d, then p(z)/q(z) = p,(s)/q,(z) for some n. For if d,-2 > d 2 dn–l, there are solutions q(x) with deg(q) = en-l + d -4-l < en, and we have proved that all solutions of such low degree have the stated property.] SECTION 4.6.2 1. By the principle of inclusion and exclusion (Section 1.3.3), the number of poly- nomials without linear factors is Ckcn (:)~ -~(-l)~ = pn-P(p -1)P. The stated probability when n 2 p is therefore 1 I- (1 -l/p) , which is greater than $. [In fact, the stated probability is greater than 4 for all n 2 1.1 The average number of linear factors is p times the average number of times 2 is a factor, so it is A(1 -p- ) = 1+p++...+p -n. [See answer 38 for further comments on the average number of linear factors.] 2. (a) We know that U(X) has a representation as a product of irreducible polynomials; and the leading coefficients of these polynomials must be units, since they divide the leading coefficient of U(Z). Therefore we may assume that U(X) has a representation as a product of manic irreducible polynomials pl(~)~l . . .P~(x)~~, where PI(Z), . . , ~~(5) are distinct. This representation is unique, except for the order of the factors, so the conditions on U(Z), W(Z), u)(z) are satisfied if and only if w(x) = pl(s) el 2 . .p,(z) y W(Z) = pl(z)elmod2...p,(2)e,mod2. (b) The generating function for the number of manic polynomials of degree n is 1+pz+p222+. . . = l/( 1 -pz). The generating function for the number of polynomials of degree n having the form v(x)~, where V(Z) is manic, is 1 + pz2 + p2z4 + = l/(1 -pz2). If the generating function for the number of manic squarefree polynomials of degree n is q(z), then by part (a) we must have l/(1 -pz) = g(z)/(l -pz2). Hence g(z) = (1 -pz2)/(1 -pz) = 1 + pz + (p -p)z2 + (p -p2)z3 $ . . . . The answer is pLp-l for n 2 2. [Curiously, this proves that gcd(u(s), U (Z)) = 1 with probability 1 -l/p; it is the same as the probability that gcd(u(a), V(X)) = 1 when U(X) and U(Z) are independent, by exercise 4.6.1-5.1 Note: By a similar argument, every U(X) has a unique representation v(z)w(s)~, where W(Z) is not divisible by the rth power of any irreducible; the number of such manic polynomials V(X) is p -pn- +l for 12 > r. 3. Let U(Z) = Us.. . Us. There is at most one such W(X), by the argument of Theorem 4.3.26. There is at least one if, for each j, we can solve the system with ~~(2) = 1 and wk(z) = 0 for ,&z # j. A solution to the latter is 2)1(z)n~~~Uk(2), where w,(z) and We can be found satisfying w1(z) nkfj uk(z) + w2(z)74(2) = 1, deg(w ) < Mu,), by the extension of Euclid s algorithm (exercise 4.6.1-3).