Continued fractionsin -stage Euclidean quadratic fields

Authors:
Xavier Guitart and Marc Masdeu

Journal:
Math. Comp. **82** (2013), 1223-1233

MSC (2010):
Primary 13F07, 11A55

Published electronically:
October 15, 2012

MathSciNet review:
3008856

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We discuss continued fractions on real quadratic number fields of class number . If the field has the property of being -stage euclidean, a generalization of the euclidean algorithm can be used to compute these continued fractions. Although it is conjectured that all real quadratic fields of class number are -stage euclidean, this property has been proven for only a few of them. The main result of this paper is an algorithm that, given a real quadratic field of class number , verifies this conjecture, and produces as byproduct enough data to efficiently compute continued fraction expansions. If the field was not -stage euclidean, then the algorithm would not terminate. As an application, we enlarge the list of known -stage euclidean fields, by proving that all real quadratic fields of class number and discriminant less than are -stage euclidean.

**1.**George E. Cooke,*A weakening of the Euclidean property for integral domains and applications to algebraic number theory. I*, J. Reine Angew. Math.**282**(1976), 133–156. MR**0406973****2.**George E. Cooke,*A weakening of the Euclidean property for integral domains and applications to algebraic number theory. II*, J. Reine Angew. Math.**283/284**(1976), 71–85. MR**0406974****3.**George Cooke and Peter J. Weinberger,*On the construction of division chains in algebraic number rings, with applications to 𝑆𝐿₂*, Comm. Algebra**3**(1975), 481–524. MR**0387251****4.**J. E. Cremona,*Hyperbolic tessellations, modular symbols, and elliptic curves over complex quadratic fields*, Compositio Math.**51**(1984), no. 3, 275–324. MR**743014****5.**Henri Darmon and Adam Logan,*Periods of Hilbert modular forms and rational points on elliptic curves*, Int. Math. Res. Not.**40**(2003), 2153–2180. MR**1997296**, 10.1155/S1073792803131108**6.**H. Davenport,*Indefinite binary quadratic forms, and Euclid’s algorithm in real quadratic fields*, Proc. London Math. Soc. (2)**53**(1951), 65–82. MR**0041883****7.**Lassina Dembélé,*An algorithm for modular elliptic curves over real quadratic fields*, Experiment. Math.**17**(2008), no. 4, 427–438. MR**2484426****8.**L. Dembélé, J. Voight,*Explicit methods for Hilbert modular forms.*To appear in ``Elliptic Curves, Hilbert modular forms and Galois deformations''.`arXiv:1010.5727v2.`**9.**Veikko Ennola,*On the first inhomogeneous minimum of indefinite binary quadratic forms and Euclid’s algorithm in real quadratic fields*, Ann. Univ. Turku. Ser. AI**28**(1958), 58. MR**0097356****10.**G. H. Hardy and E. M. Wright,*An introduction to the theory of numbers*, 6th ed., Oxford University Press, Oxford, 2008. Revised by D. R. Heath-Brown and J. H. Silverman; With a foreword by Andrew Wiles. MR**2445243****11.**Franz Lemmermeyer,*The Euclidean algorithm in algebraic number fields*, Exposition. Math.**13**(1995), no. 5, 385–416. MR**1362867**

Retrieve articles in *Mathematics of Computation*
with MSC (2010):
13F07,
11A55

Retrieve articles in all journals with MSC (2010): 13F07, 11A55

Additional Information

**Xavier Guitart**

Affiliation:
Department of Mathematics, Universitat Politècnica de Catalunya, Barcelona, Spain

Email:
xevi.guitart@gmail.com

**Marc Masdeu**

Affiliation:
Department of Mathematics, Columbia University, New York, New York 10001

Email:
masdeu@math.columbia.edu

DOI:
http://dx.doi.org/10.1090/S0025-5718-2012-02620-2

Received by editor(s):
June 4, 2011

Received by editor(s) in revised form:
September 6, 2011

Published electronically:
October 15, 2012

Additional Notes:
This work was partially supported by Grants MTM2009-13060-C02-01 and 2009 SGR 1220.

Article copyright:
© Copyright 2012
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.