4.5.3 ANALYSIS OF EUCLID S (Web site construction) ALGORITHM 359 11. [A&?01
4.5.3 ANALYSIS OF EUCLID S ALGORITHM 359 11. [A&?01 (J. Lagrange.) Let X = .& + /Al,Az, . . . /, Y = BCJ + /&?I, &, . . . / be the regular continued fraction representations of two real numbers X and Y, in the sense of exercise 10. Show that these representations Iln the sense that &+k = &+k for some m and n and for all y if we have X = (qY + r)/(sY + t) for some integers q, r, s, t with(qt -rsl = 1. (This theorem is the analog, for continued fraction representations, of the simple result that X and Y in the decimal system eventually agree if and only if for some integers q, r, and s.) b 12. [A&o] A quadratic irrationality is a number of the form (a -U)/V, where D, U, and V are integers, D > 0, V # 0, and D is not a perfect square. We may assume without loss of generality that V is a divisor of D -U2, for otherwise the number may be rewritten as (m -UlVl)/VlVl. a) Prove that the regular continued fraction expansion (in the sense of exercise 10) of a quadratic irrationality X = (a -U)/V is obtained by the following formulas: v-0 = v, A0 = 1×1, iY0 = u+Aov; &+I = (D -U, )/K, An+1 = 1@+ Un)/Vn+1J, U n+1–An+lK+l -Un. [Note: An algorithm based on this process has many applications to the solution of quadratic equations in integers; see, for example, H. Davenport, The Higher Arithmetic (London: Hutchinson, 1952); W. J. LeVeque, Topics in Number Theory (Reading, Mass.: Addison-Wesley, 1956); and see also Section 4.5.4. By exercise 1.2.4-35, we have An+1 = 1(1×6] + U,)/V,+lJ when K+I > 0, and A,+1 = l(lfij + 1+ &)/K+lJ when V n+l < 0; hence such an algorithm need only work with the positive integer [fi].] b) Prove that 0 < U, < ~6, 0 < V,, < 2fi, f or all n > N, where N is some in- teger depending on X; hence the regular continued fraction representation of every quadratic irrationality is eventually periodic. [Hint: Show that (—a -U)/V = &+/A,…, A, -Vn/(fi+UJ, and use Eq. (5) to prove that (a+ Un)/Vn is positive when n is large.] c) Letting p, = Qn+l(Ao, AI,. . . , An) and qn = Qn(A1,. . . ,An), prove the identity VP: + 2Upnqn + ((U -D)/V)q: = (-l) +lK+~. d) Prove that the regular continued fraction representation of an irrational number X is eventually periodic if and only if X is a quadratic irrationality. (This is the continued fraction analog of the fact that the decimal expansion of a real number X is eventually periodic if and only if X is rational.) 13. [M40] (J. Lagrange, 1797.) Let f(z) = u~z +…+uo, a, > 0, be a polynomial with integer coefficients, having no rational roots, and having exactly one real root 6 > 1. Design a computer program to find the first thousand or so partial quotients of [, using the following algorithm (which essentially involves only addition): Ll. Set A c 1. L2. For k = 0, 1, . . . , n -1 (in this prder) and for j = n -1, . . . , Ic (in this order), set aj +- uj+l + aj. (This step replaces f(s) by g(s) = f(z + l), a polynomial whose roots are one less than those of f.) L3. If a, + a,-1 + . . . + uo < 0, set A c A + 1 and return to L2.