352 ARITHMETIC 4.5.3 Theorem E. Let n and (Virtual web hosting)
352 ARITHMETIC 4.5.3 Theorem E. Let n and k be positive integers, and let pk(a, n) be the probability that the (k + 1)st quotient Ak+l in Euclid s algorithm is equal to a, when 2, = n and u is chosen at random. Then lim pk(a, n) = Fk n+co where Fk(z) is the distribution function (21). Proof. The set I of all X in [ 0,l) for which Ak+l = a is a union of disjoint intervals, and so is the set J of all X for which Ak+l # a. Lemma M therefore applies, with K the set of all X for which Ak+l is undefined. Furthermore, Fk(l/u) -Fk(l/(u + 1)) is the probability that l/(u + 1) < X, 2 l/u, which is p(I), the probability that Ak+l = a. 1 As a consequence of Theorems E and W, we can say that a quotient equal to a occurs with the approximate probability lg(l + l/a) - k(l + ll(a + 1,) =k@ + l) l((~ + v - 1)). Thus a quotient of 1 occurs about lg(f) = 41.504 percent of the time; a quotient of 2 occurs about lg($) = 16.992 percent of the time; a quotient of 3 occurs about lg($$) = 9.311 percent of the time; a quotient of 4 occurs about lg(g) = 5.890 percent of the time. Actually, if Euclid s algorithm produces the quotients Al, AZ, . . . , At, the nature of the proofs above will guarantee this behavior only for Ak when k is comparatively small with respect to t; the values At-l, At-z, . . . are not covered by this proof. But we can in fact show that the distribution of the last quotients At-l, At-z, . . . is essentially the same as the first. For example, consider the regular continued fraction expansions for the set of all proper fractions whose denominator is 29: &J = 1291 & =/3,1,1,&a/ &$ = /1,1,14/ g = /1,3,7/ &=/14,2/ &=/3,4,2/ i$ = /1,1,4,3/ $3 = / 1,3,L 5/ i$=/g,w +$=/2,1,9/ g = / 1, 1,2,2, a/ g = /1,4,1,4/ 2% = 17941 j-$ =/2,1,1,1,3/ # =/1,1,1,1,1,3/ @i =/1,6,4/ & = /5,1,4/ &j = /2,2,2,2/ % = /111,1,9/ j$ = / 1,&l, 2/ &=/4,1,5/ #=/2,4,3/ %I$= / 1,2,4,2/ g = / 1,13,2/ Jg = 14971 +j = / 2,14/ g = /1,2,1,1,1,2/ 3 = /1,28/ Several things can be observed in this table.