Apache web server for windows - 618 ANSWERS TO EXERCISES 4.6.1 4. Since the
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.