4.5.3 ANALYSIS OF EUCLID S ALGORITHM 351 Lemma M. Let J1, Jz, . . . be pairwise disjoint isltervals contained in the interval [ 0,l IJ u Ik, J= u J/c, K = (0, 11 (I u J). ;k>l k>l Assume that K4as measure zero. Let P, be the set (O/n, l/n,. . . , (n -1)/n}. Then / lim III nPntI = p(I). n–+00 n (43) Here ~(1) is the qebesgue measure of I, namely, ck> 1 length(&); and III fl P,ll denotes the number of elements in the set 1 n P,. - Proof. Let IN 4= U l 0, find N large enough so that P( IN) -I- P( JN) 2 1 -E, and let KN=K u u Ik u u Jk. k>N k>N If I is an intervdl, having any of the forms (a, b) or [a, b) or (a, b] or [a, b], it is clear that ~(1) 4 b -a and v-44–l I lImPnIl 2 v-44+1. Now let TV = II& n Pm/l, sn = [[JN n Pnll, t, = IIKN n %(I; we have Hence = 1 -t 5 1 - /.L(JN) + X 5 p(I) j-z + E. This holds for al/ n and for all E; hence limn+,a, Tn/n = p(l). 1 I Exercise 25 hows that Lemma M is not trivial, in the sense that some rather restrictive hypot 1 eses are needed to prove (43). quotients. Now we can put Theorem W and Lemma M some solid facts about Euclid s algorithm.
This entry was posted
on Monday, February 11th, 2008 at 10:14 pm and is filed under J2EE.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.