Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Continued fractions and linear recurrences

Authors: H. W. Lenstra and J. O. Shallit
Journal: Math. Comp. 61 (1993), 351-354
MSC: Primary 11A55; Secondary 11B37
MathSciNet review: 1192972
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We prove that the numerators and denominators of the convergents to a real irrational number $ \theta $ satisfy a linear recurrence with constant coefficients if and only if $ \theta $ is a quadratic irrational. The proof uses the Hadamard Quotient Theorem of A. van der Poorten.

References [Enhancements On Off] (What's this?)

  • [1] J. S. Frame, Classroom Notes: Continued Fractions and Matrices, Amer. Math. Monthly 56 (1949), no. 2, 98–103. MR 1527170, 10.2307/2306169
  • [2] G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR 568909
  • [3] G. Pólya and G. Szegö, Problems and theorems in analysis II, Springer-Verlag, Berlin and New York, 1976.
  • [4] A. J. van der Poorten, 𝑝-adic methods in the study of Taylor coefficients of rational functions, Bull. Austral. Math. Soc. 29 (1984), no. 1, 109–117. MR 732178, 10.1017/S0004972700021328
  • [5] Alfred J. van der Poorten, Solution de la conjecture de Pisot sur le quotient de Hadamard de deux fractions rationnelles, C. R. Acad. Sci. Paris Sér. I Math. 306 (1988), no. 3, 97–102 (French, with English summary). MR 929097
  • [6] Robert Rumely, Notes on van der Poorten’s proof of the Hadamard quotient theorem. I, II, Séminaire de Théorie des Nombres, Paris 1986–87, Progr. Math., vol. 75, Birkhäuser Boston, Boston, MA, 1988, pp. 349–382, 383–409. MR 990517

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11A55, 11B37

Retrieve articles in all journals with MSC: 11A55, 11B37

Additional Information

Keywords: Continued fractions, linear recurrences
Article copyright: © Copyright 1993 American Mathematical Society