MySQL Web Server, Tomcat, Jsp, Struts Hosting Blog

4.6.2 ANSWERS TO EXERCISES 627 20. (a) C(CYU~ -113–1)(~!o, -UJml) = C(uJ -cYu3–1)(ELj -cxti3-1). (b) We may assume that UCI # 0. Let m(u) = n,<,I,min(l, 1~~1) = z~~/M(u)u,. Whenever /cx,~ < 1, change the factor CC-(Ye to C&z -1 in U(X); this doesn t affect Iu(. Now looking at the leading and trailing coefficients only, we have 1~1 2 Junl m(u) + l~,12A4(u)2; hence we obtain the slightly stronger result Mu 5 (1~1 + (1~1 - 41~o~,12)l'2)/2)~~12. [A further improvement in the estimate of M(u) can often be obtained by replacing U(Z) by the polynomial C(z) = (z -sk/lul )u(z), where Sk = c,$ u-k; since M(c) = M(U) and ICI2 = 12~)~ - lsk12/Iu12, we obtain the inequality )u12 -ISkl /luI 2 IU0121Sk12/((U)4M(2L)2) + (u,~~M(u)~ for 1 < k < n. In the case of polynomial (22), we have s2 = -72 and we obtain the bound M(u) < 8.1837.1 (c) ZL~ = urn c a%1 . . . CY~,-~, an elementary symmetric function, hence Juj I 5 Iurn1 ~/A, b,-, where I4 = max(1, Ia,I). We complete the proof by showing that when ~1 2 1, , zn 2 1, and 51.. Z~ = M, the elementary symmetric function ffnk = C&I.. .x,k is 5 (;Ii)M + (nkl), the value assumed when x1 = . . . = x+-1 = 1 and xn = M. (For if x1 2 ... 2 xn < M, the transformation xn + Xn-lXnr Xn-1 + 1 increases onk by o(n-2)(k-1)(z, -1)(x%-1 -I), which is positive.) (4 1~1 I ~J~I(( J-~)WV) + (:I:)) 5 l~l((~~~)M(u) + ( jIi )> since lwml I lunl and M(v) 2 M(u). [See J. Vicente Goncalves, Revista de Faculdade de Ci&ncias (2) A 1 (Univ. Lisbon, 1950), 167-171; M. Mignotte, Math. Comp. 28 (1974), 1153-1157; Mignotte and Payafar, R.AZRO Analyse numCr. 13 (1979), 181-192.1 21. (a) /d(%e(ne) + … + uo)(&e(-no) + … + @)d8 = 1~~~1~ +. + 12~01~ since si e(jO)e(-ke) d6 = 63k; now use induction on t. (b) Since 1~~) 5 ( j)M(u)Iu-1 we con- clude that )w12 5 (2~)M(~)21vm)2. Hence ~~~2~20~2 5 (2z)(2,k)M(V)2M(W)21?JmZUk12 = f(m, k)M(u)2/u,12 < f(m, k)lu12. [Slightly better values for f(m, k) are possible based on the more detailed information in exercise 20.1 (c) The case t = 3 suffices to show how to get from t -1 to t. When t = 2 we have shown that, for all ol, !d !b so1 so1 / (e(h), e(h), e(43))~ ~~(e(~l), 4@2), e(ti3))1 d42 d43 dQ2 W3 5 f(w, b)f(m, h) so1 so1 Iv(e(h), 4% e(e3))/ lw(e(s,), e(b), e(&))12 de2 de3. For all 42, $3, $2, 7,!+ we have also shown that so1 so1 Iv(44lh e(b), 4h))12/44@l), e(h), 4@3)))2 d#l WI I .f(m,k~)~~~ lv(e(e1),e(~2),e(~3))12lw(e(e1),e(~2),e(~3))(2de1. Integrate the former inequality with respect to e1 and the latter with respect to @2, c#J~, 7+!~2, $3. [This method was used by A. 0. Gel fond in Transcendental and Algebraic Numbers (New York: Dover, 1960), Section 3.4, to derive a slightly different result.] 22. More generally, assume that u(x) E v(x)w(x) (modulo q), a(x)w(x)+b(x)w(x) s 1 (modulo p), and cl(w) = 1 (modulo r), deg(a) < deg(zu), deg(b) < deg(w), deg(u) = deg(w) + deg(w), where r = gcd(p, q) and p, q needn t be prime. We shall construct polynomials V(x) = w(z) and W(z) = W(Z) (modulo q) such that U(X) E V(x)W(x) (modulo qr), t(V) = e(v), deg(V) = deg(w), deg(W) = deg(w); furthermore, if r is prime, the results will be unique modulo qr. The problem asks us to find e(x) and a(x) with V(x) = w(x) + qe(x), W(x) = w(x) + q$x), deg(ti) < deg(w), deg(ti) 5 deg(w); and the other condition (w(x) + qG))(w(x) + @4x)) = 4×1 (module v)

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.

4.6.2 ANSWERS TO EXERCISES 625 11. Removing the trivial factor 2, the matrix Q -I on the previous page has a null space generated by (l,O, O,O,O, 0,O) and (0,3,1,4,1,2,1). The factorization is x(x + 3x + 4)(x5 + 2×4 + x3 + 4×2 + 2 + 3). 12. If p = 2, (Z + 1)4 = x4 + 1. If p = 8k + 1, Q -I is the zero matrix, so there are four factors. For other values of p we have p=8k+3 p=8k+5 p=8k+7 Q-I=(+)(;-; ;i;)(ij-;j) Here Q-I has rank 2, so there are 4-2 = 2 factors. [But it is easy to prove that x4 f 1 is irreducible over the integers, since it has no linear factors and the coefficient of z in any factor of degree two must be less than or equal to 2 in absolute value by exercise 20. For all k 2 2, H. P. F. Swinnerton-Dyer has exhibited polynomials of degree 2k that are irreducible over the integers, but they split completely into linear and quadratic factors modulo every prime. For degree 8, his example is Z -16s6 $ 88×4 f 192×2 + 144, having roots &fi f x/ ? f i [see Math. Comp. 24 (1970), 733-7341. According to the theorem of Frobenius cited in exercise 37, any irreducible polynomial of degree n whose Galois group contains no n-cycles will have factors modulo almost all primes.] 13. p = 8k + 1: (x + (1 + d=$/d )(x + (1 -&$/6)(x -(1 + J=i)/v z)x (x -(1 -a)/& ). p = 8kf3: (x2 -mx -l)(? -v =% -1). p = 8kf5: (x2 -&3)(x -J-i). p = 8k + 7: (x2 -fix + 1)(x2 + fix + 1). The latter factorization also holds over the field of real numbers. 14. Algorithm N can be adapted to find the coefficients of w: Let A be the (r + 1) X n matrix whose kth row contains the coefficients of w(x) modu(x), for 0 5 k 5 7. Apply the method of Algorithm N until the first dependence is found in step N3; then the algorithm terminates with w(x) = ~0 + ~12 + . . + ukxk, where Us is defined in (18). At this point 2 < k < r; it is not necessary to know r in advance, since we can check for dependency after generating each row of A. 15. We may assume that u # 0 and that p is odd. Berlekamp s method applied to the polynomial 2 -u tells us that a square root exists if and only if u(~- ) ~ mod p = 1; let us assume that this condition holds. Let p -1 = 2e . q, where q is odd. Zassenhaus s factoring procedure suggests the following square-root extraction algorithm: Set t + 0. Evaluate gcd((x + t) -1, x2 -u), gcd((x + t)29 -1, x2 -ZL), gcd((z + t)49 -1, x2 -u), gcd((x + t) -1, x2 -u), . . , until finding the first case where the gcd is not 1 (modulo p). If the gcd is x -w, then q ?i = fw. If the gcd is x2 -u, set t + t + 1 and repeat the calculation. Notes: If (x + t) mod (x2 -U) = ux + b, then we have (x + t)kfl mod (x -u) = (b+at)x+(bt+uu), and (~+t)~~rnod(~~ -u) = 2abx+(b2 +a2u); hence (x+t) , (x + tp, . . are easy to evaluate efficiently, and-the calculation for fixed t takes O((logp)3) units of time. The square root will be found when t = 0 with probability

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+

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).

622 ANSWERS TO EXERCISES 4.6.1 For the stated example, the algorithm yields (i t) = (i z)( i -T), (i f) = (i z)( A -f), (A -i) = (!, -i)( i + (y i)( i T). (Actually any matrix with determinant fl would be a gcrd in this particular case.) 20. It may be helpful to consider the construction of exercise 4.6.2-22, with pm replaced by a small number E. 21. Note that Algorithm R is used only when m-n 5 1; furthermore, the coefficients are bounded by (25) with m = n. [The stated formula is, in fact, the execution time observed in practice, not merely an upper bound. For more detailed information see G. E. Collins, Proc. 1968 Summer Inst. on Symbolic Math. Camp., Robert G. Tobey, ed. (IBM Federal Systems Center: June 1969), 195-231.1 22. A sequence of signs cannot contain two consecutive zeros, since uk+l(x) is a nonzero constant in (29). Moreover we cannot have +, 0, + or -, 0, - as subsequences. The formula V(u, a) -V(u, b) is clearly valid when b = a, so we must only verify it as b incfeases. The polynomials ~~(2) have finitely many roots, and V(u, b) changes only when b encounters or passes such roots. Let 5 be a root of some (possibly several) u3. When b increases from 2 -E to 5, the sign sequence near j goes from +, -j-, - to +, 0, - or from -, f, + to -, 0, + if j > 0; and from +, - to 0, - or from -, + to 0, + if j = 0. (Since u (x) is the derivative, u (x) is negative when U(Z) is decreasing.) Thus the net change in V is -S,,. When b increases from 3: to z + E, a similar argument shows that V remains unchanged. [L. E. Heindel, JACM 18 (1971), 533-548, has applied these ideas to construct algorithms for isolating the real zeros of a given polynomial u(x), in time bounded by a polynomial in deg(u) and log N, where all coefficients yJ are integers with Iuj( 5 N, and all operations are guaranteed to be exact.] 23. If v has n-l real roots occurring between the n real roots of U, then (by considering sign changes) U(X) mod W(Z) has n -2 real roots lying between the n -1 roots of w. 24. First show that hj = g~-1g~~;2(1-6~-1). ~~ -62 . 1-63- . Then show that the exponent of g2 on the left-hand side of (18) has the form 62 + 61x, where 2 = 62 + . . . + 6,-l + 1 - 62(63 + . . + sj-1 + 1) -&(l -62)(& + . . . + f5–1 + 1) - . . . -6,-1(1 -62). (1 -6,-2)(l). B u t x = 1, since it is seen to be independent of S,-, and we can set Sj+1 = 0, etc. A similar derivation works for gs, g4, . , and a simpler derivation works for (23). 25. Each coefficient of U?(X) can be expressed as a determinant in which one column contains only e(u), e(v), and zeros. To use this fact, modify Algorithm C as follows: In step Cl, set g + gcd(e(zl),e(v)) and h + 0. In step C3, if h = 0, set u(x) + V(X), V(X) c r(x)/g, h c e(u)6/g, g t e(u), and return to C2; otherwise proceed as in the unmodified algorithm. The effect of this new initialization is simply to replace Us by uj(x)/gcd(!(zl), e(w)) for all j 2 3; thus, 1 j- will become f?23-5 in (28). 26. In fact, even more is true. Note that the algorithm in exercise 3 computes &P~(z) and Tqn(s) for n 2 -1. Let e, = deg(q,) and d, = deg(p,u -qnv); we observed in exercise 3 that d,-1 + e, = deg(u) for n 2 0. We shall prove that the conditions deg(q) < e, and deg(pu -qv) < d,-2 imply that p(x) = c(x)p,-l(x) and q(z) = c(z)qn-l(z): Given such p and q, we can find c(x) and d(x) such that p(x) = c(x)P~-I(x) + d(x)pn(x) and q(x) = c(x)q+l(x) + d(x)q,(x), since pn-l(x)qn(x) - p,(z)q,--l(s) = fl. Hence pu-qv = c(p,-lu-qq,-lw)+d(p,u-qq,w). If d(x) # 0, we must have deg(c) + e,-1 = deg(d) + e,, since deg(q) < deg(q,); it follows that deg(c) + d,-1 > deg(d) + d,, since this is surely true if d, = -co and otherwise we

4.6.1 ANSWERS TO EXERCISES 621 C3. Find Q and R such that ~1 = Qvz + R, where deg(R) < deg(wz). (We have w(Q2r2 + R) = 2~2712, so ulR = (2~2 -u1Q)v2 = R wz.) C4. Set (WI, w2, w:, w;, a, ~2, z:, zl,, UI, u2, WI, 7~2) + (w: -WIQ, w z -w2&, WI, wz, z;, zk, zl -Qz:, z2 -Qz/,, 212 - ZL~&, ~1, 2)2, ~1 -Qw2) and n + n + 1. Go back to C2. m This extension of Euclid s algorithm includes most of the features we have seen in previous extensions, all at the same time, so it provides new insight into the special cases already considered. To prove that it is valid, note first that deg(v2) decreases in step C4, so the algorithm certainly terminates. At the conclusion of the algorithm, v1 is a common right divisor of Vl and V2, since wlvl = (-l)nV1 and -w2w1 = (-l)nV2; also if d is any common right divisor of VI and V2, it is a right divisor of zlV1 + z2V2 = ol. Hence w1 = gcrd(K, V,). Also if m is any common left multiple of Vl and Vz, we may assume without loss of generality that m = UlVl = U2V.2, since the sequence of values of Q does not depend on Ul and U2. Hence m = (-l) (--u2z~)Vl = (-1) (u2z~)V2 is a multiple of zi VI. In practice, if we just want to calculate gcrd(Vl,Vz), we may suppress the com- putation of n, WI, ~2, wi, w& zl, ~2, zi, 2;. These additional quantities were added to the algorithm primarily to make its validity more readily established. Note: Nontrivial factorizations of string polynomials, such as the example given with this exercise, can be found from matrix identities such as (f x ix: x -:x -3c -3 =(:, 3 since these identities hold even when multiplication is not commutative. For example, (abc + a + c)(l + ba) = (ab + l)(cba + a + c). (Compare this with the continuant polynomials of Section 4.5.3.) 19. [Cf. Eugene Cahen, TMorie des AJombres 1 (Paris: A. Hermann & fils, 1914), 336-338.1 If such an algorithm exists, D is a gcrd by the argument in exercise 18. Let us regard A and B as a single 2n X n matrix C whose first n rows are those of A, and whose second n rows are those of B. Similarly, P and Q can be combined into a 2n X n matrix R; X and Y can be combined into an n X 2n matrix 2. The desired conditions now reduce to two equations C = RD, D = ZC. If we can find a 2n X 2n integer matrix U with determinant fl such that the last n rows of U- C are all zero, then R = (first n columns of U), D = (first n rows of U-lC), Z = (first n rows of U- ) solves the desired conditions. Hence, for example, the following algorithm may be used (with m = 2n): Algorithm T (Triangularization). Let C be an m X n matrix of integers. This algorithm finds m X m integer matrices U and V such that UV = I and VC is upper triangular. (The entry in row i and column j of VC is zero if i > j.) Tl. [Initialize.] Set U +-V +-I, the m X m identity matrix; and set T + C. (Throughout the algorithm we will have T = VC and UV = 1.) T2. [Iterate on j.] Do step T3 for j = 1, 2, . . . , min(m, n), and terminate the algorithm. T3. [Zero out column j.] Perform the following transformation zero or more times until Tij is zero for all i > j: Let Tkj be a nonzero element of { Tzj , T(,+l), , . , T,, } having the smallest absolute value. Interchange rows Ic and j of T and of V; interchange columns Ic and j of U. Then subtract LTij/TjjJ times row j from row i, in matrices T and V, and add the same multiple of column. i to column j in matrix U, for j < i 5 m. 1

620 ANSWERS TO EXERCISES 4.6.1 15. Let cij = aiiajl + . . . + a,,ajn; we may assume that czZ > 0 for all i. If cZ3 # 0 for some i # j, we can replace row i by (a,~ -caJr,. . , uZn. -cajn), where c = c,,/c,,; this does not change the value of the determinant, and it decreases the value of the upper bound we wish to prove, since cii is replaced by cii -&/c2j. These replacements can be done in a systematic way for increasing i and for j < i, until czj = 0 for all i # j. [The latter algorithm is called Schmidt s orthogonalization process ; see Math. Annden 63 (1907), 442.1 Then det(A) = det(AAT) = ~11 cnn. 16. Let f(zi, . , zn) = gm(zz, , s,)zy + . + go(sz, . . , xn) and g(sz, . . . , 2,) = gm(22,. . . , 2n)2 + . . . + go(ra, . . , 2%) ; the latter is not identically zero. We have aN 5 m(2N + I)+’ $ (2N + l)bN, where bN counts t,he integer solutions of g(za, . . . , xn) = 0 with variables bounded by JV. Hence limN,, aN/(zN + 1) = limN+co b.w/(aN + l)n-l, and this is zero by induction. 17. (a) For convenience, let us describe the algorithm only for A = {a, b}. The hy- potheses imply that deg(QlU) = deg(QaV) 2 0, deg(Qi) 5 deg(Qz). If deg(Qi) = 0, then Qr is just a nonzero rational number, so we set Q = &a/&i. Otherwise we let &I = U&II -I– b&12 + rl, Qz = aQzl + b&22 + ra, where ri and rz are rational numbers; it follows that &IV -Q2V = a(QllU -QzlV) + b(Q12U _ Q22v) + rlU _ r2v. We must have either deg(Qrr) = deg(Qi) -1 or deg(Qia) = deg(Qi) -1. In the former case, deg(QiiU -QzlV) < deg(QiiU), by considering the terms of highest degree that start with a; so we may replace Qi by &ii, &a by Q2r, and repeat the process. Similarly in the latter case, we may replace (Qi, Q2) by (Qia, Q22) and repeat the process. (b) We may assume that deg(U) 2 deg(V). If deg(R) 2 deg(V), note that &IV -Q2V = QiR -(Qz -Q1Q)V has degree less than deg(V) 2 deg(QrR), so we can repeat the process with U replaced by R; we obtain R = Q V + R , U = (Q + Q )V + R , where deg(R ) < deg(R), so eventually a solution will be obtained. (c) The algorithm of (b) gives VI = UV2 +R, deg(R) < deg(V2); by homogeneity, R = 0 and U is homogeneous. (d) We may assume that deg(V) 5 deg(U). If deg(V) = 0, set W + U; otherwise use (c) to find U = QV, so that QVV = VQV, (QV -VQ)V = 0. This implies that QV = VQ, so we can set U + V, V t Q and repeat the process. For further details about the subject of this exercise, see P. M. Cohn, Proc. Cambridge Phil. Sot. 57 (1961), 18-30. The considerably more difficult problem of characterizing all string polynomials such that UV = VU has been solved by G. M. Bergman [Ph.D. thesis, Harvard University, 19671. 18. [P. M. Cohn, Transactions Amer. Math. Sot. 109 (1963), 332-356.1 Cl. Set ui + Ul, 2~2 + U2, u1 + VI, v2 + V2, z1 + 2; + WI + wh + 1, Z: + 22 t w; + w2 + 0, n + 0. C2. (At this point the identities given in the exercise hold, and uivi = 1~1~12; vz = 0 if and only if ui = 0.) If 212 = 0, the algorithm terminates with gcrd(Vi , V2) = VI, lclm(Vi,Va) = z:V, = -2LV2. (Also, by symmetry, we have gcld(Ui,Us) = ILL and lcrm(Ui, Uz) = Uizui = -U2w2.)

4.6.1 ANSWERS TO EXERCISES 619 10. By successively factoring reducible polynomials into polynomials of smaller de- gree, we must obtain a finite factorization of any polynomial into irreducibles. The factorization of the content is unique. To show that there is at most one factorization of the primitive part, the key result is to prove that if U(Z) is an irreducible factor of w(z)w(z), but not a unit multiple of the irreducible polynomial w(x), then U(Z) is a fac- tor of W(Z). This can be proved by observing that U(Z) is a factor of w(~)w(x)U(z) = T W(X) -w(z)u(z)V(z) by the result of exercise 9, where r is a nonzero constant. 11. The only row names needed would be AI, Ao, B4, Bs, Bz, BI, Bo, Cl, Co, Do. In general, let u~+~(z) = 0; then the rows needed for the proof are A,,-,, through Ao, B,,-,, through Ro, C,,-,, through CO, D,,-,, through Do, etc. 12. If nk = 0, the text s proof of (24) shows that the value of the determinant is *hk, and this equals *e;k-ll nlcjck e,”l-1(63-1) . If the polynomials have a factor of positive degree, we can artificially assume that the polynomial zero has degree zero and use the same formula with & = 0. Notes: The value R(u, w) of Sylvester s determinant is called the resultant of u and w, and the quantity (-l)deg( )(d g( )- )/2e(U)-1R( IL, u ) is called the discriminant of U, where U is the derivative of U. If U(Z) has the factored form a(z -al). . . (Z -cym), and if W(Z) = b(z -PI). . (Z -&), the resultant R(u,w) is anw(~l). . .w(ar,) = (-l) b u(&) . . . u&) = anbm n l

618 ANSWERS TO EXERCISES 4.6.1 4. Since the quotient q(s) depends only on W(Z) and the first m -n coefficients of U(Z), the remainder T(X) U(Z)-q( w z is uniformly distributed and independent of = z ) ( ) V(Z). Hence each step of the algorithm may be regarded as independent of the others; this algorithm is much more well-behaved than Euclid s algorithm over the integers. The probability that ni = n -k is ~ ~~(1 -l/p), and t = 0 with probability P -m. Each succeeding step has essentially the same behavior; hence we can see that any given sequence of degrees n, nl, . . , nt, -co occurs with probability (p -l)t/pn. To find the average value of f(nl, . . . , nt), let St be the sum of f(nl, . . . , nt) over all sequences n > ni > … > nt 2 0 having a given value of t; then the average is c, WP -lYIPn. Let f(nl,. . ,nt) = t; then St = (;)(t + l), so the average is n(1 -l/p). Similarly, if f(nr , . . . , nt) = nr + … + nt, then St = (;)(:1:), and the average is (y)(l-l/p). Finally, if f(nl,…,nt) = (n-nl)nl +…-+-(nt-, -nt)nt, then St = [:g)~:;~i y(yj+>,(n$ )($ and the average is (?l) -(n -t-~)P/(P -1) -I- P P As a consequence we can see that if p is large there is very high probability that n,+l = nn3 - 1 for all j. (If this condition fails over the rational numbers, it fails for all p, so we have further evidence for the text s claim that Algorithm C almost always finds 15~ = = 1.) 5. Using the formulas developed in exercise 4, with f(ni, , nt) = &0, we find that the probability is 1 -l/p if n > 0, 1 if n = 0. 6. Assuming that the constant terms ~(0) and w(0) are nonzero, imagine a right-to- left division algorithm, U(Z) = w(z)q(z) + z~-?(z), where deg(r) < deg(w). We obtain a gcd algorithm analogous to Algorithm 4.5.2B, which is essentially Euclid s algorithm applied to the reverse of the original inputs (cf. exercise 2), afterwards reversing the answer and multiplying by an appropriate power of ZC. 7. The units of S (as polynomials of degree zero). 8. If U(Z) = w(z)w(z), where U(Z) has integer coefficients while V(X) and W(Z) have rational coefficients, there are integers m and n such that m . W(Z) and n . W(Z) have integer coefficients. Now u(x) is primitive, so we have u(z) = f w(m .wW) PP(n. 4x)). 9. We can extend Algorithm E as follows: Let (ul(z), uz(s), us, Us) and (w~(z),w~(x), ~3, We) be quadruples that satisfy the relations ur(z)u(z) + u~(z)w(z) = u~u~(x), WI(Z)U(Z) + WOW = 2132)4(z). The extended algorithm starts with the quadruples (ho, cant(u), PP(~(z))) and (0, 1, cant(v), PP(@))) an d manipulates them in such a way as to preserve the above conditions, where U,(Z) and We run through the same sequence as U(Z) and W(Z) do in Algorithm E. If au4(2) = OVA + k(s), we have a%(ul(z), m(z)) -q(z)ua(w~(s), m(z)) = (n(z), n(z)), where r,(z)u(z) + Q(Z)W(Z) = bu3w3r(z), so the extended algorithm can preserve the desired relations. If U(Z) and W(Z) are relatively prime, the extended algorithm eventually finds r(z) of degree zero, and we obtain V(Z) = Q(Z), V(z) = ~1 ( z ) as desired. (In practice we would divide Q(X), Q(Z), and bu3w3 by gcd(cont(rl), cont(rz)).) C onversely, if such U(s) and V(z) exist, then U(X) and W(Z) have no common prime divisors, since they are primitive and have no common divisors of positive degree.