Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 

 

Midpoint criteria for solving Pell's equation using the nearest square continued fraction


Authors: Keith Matthews, John Robertson and Jim White
Journal: Math. Comp. 79 (2010), 485-499
MSC (2000): Primary 11D09, 11Y50, 11A55, 11Y65
Published electronically: July 21, 2009
MathSciNet review: 2552236
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We derive midpoint criteria for solving Pell's equation $ x^2-Dy^2=\pm 1$, using the nearest square continued fraction expansion of $ \sqrt{D}$. The period of the expansion is on average $ 70%$ that of the regular continued fraction. We derive similar criteria for the diophantine equation $ x^2-xy-\frac{(D-1)}{4}y^2=\pm1$, where $ D\equiv 1\pmod{4}$. We also present some numerical results and conclude with a comparison of the computational performance of the regular, nearest square and nearest integer continued fraction algorithms.


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

  • [1] A.A.K. Ayyangar, New light on Bhaskara's Chakravala or cyclic method of solving indeterminate equations of the second degree in two variables, J. Indian Math. Soc., 18, 1929-30, pp. 225-248.
  • [2] A.A.K. Ayyangar, A new continued fraction, Current Sci. 6, June 1938, pp. 602-604. Zbl 0019.15504
  • [3] A.A.K. Ayyangar, Theory of the nearest square continued fraction, J. Mysore Univ. Sect. A. 1, (1941) 97-117. MR 0009046 (5,92d), Zbl 0060.16206, available online at http://www.ms.uky.edu/~sohum/AAK/PRELUDE.htm, July 2008.
  • [4] L.E. Dickson, History of the Theory of Numbers, Vol. 2, Chelsea AMS reprint, 1999. MR 0245500 (39:6807b)
  • [5] A. Hurwitz, Über eine besondere Art der Kettenbruch-Entwicklung reeller Grössen, Acta Math., 12, 1889, pp. 367-405. JFM 21.0188.01 MR 1554778
  • [6] K.R. Matthews and J.P. Robertson, Equality of period-lengths of nearest integer and nearest square continued fraction expansions of quadratic surds (in preparation).
  • [7] B. Minnigerode, Über eine neue Methode, die Pellsche Gleichung aufzulösen, Nachr. König. Gesellsch. Wiss. Göttingen Math.-Phys. Kl. 23, 1873, pp. 619-652. JFM 05.0105.02
  • [8] O. Perron, Die Lehre von den Kettenbrüchen, Band 1, Teubner, 1954. MR 0064172 (16:239e)
  • [9] G.J. Rieger, Über die mittlere Schrittanzahl bei Divisionsalgorithmen, Math. Nachr., 82, 1978, pp. 157-180. MR 0480366 (58:533)
  • [10] H. Riesel, On the metric theory of nearest integer continued fractions, BIT, 27, 1987, pp. 248-263. MR 0894126 (88k:11048)
  • [11] D. Shanks, Review of UMT File: Two related quadratic surds having continued fractions with exceptionally long periods, Math. Comp. 28, 1974, pp. 333-334.
  • [12] H.C. Williams, Solving the Pell equation, Proc. Millennial Conference on Number Theory, A.K. Peters, 2002, 397-435. MR 1956288 (2003m:11051)
  • [13] H.C. Williams and P.A Buhr, Calculation of the regulator of $ Q(\sqrt{d})$ by use of the nearest integer continued fraction algorithm, Math. Comp. 33, 1979, pp. 369-381. MR 0514833 (80e:12003)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11D09, 11Y50, 11A55, 11Y65

Retrieve articles in all journals with MSC (2000): 11D09, 11Y50, 11A55, 11Y65


Additional Information

Keith Matthews
Affiliation: Department of Mathematics, University of Queensland, Brisbane, Australia, 4072 and Centre for Mathematics and its Applications, Australian National University, Canberra, ACT 0200, Australia
Email: keithmatt@gmail.com

John Robertson
Affiliation: Actuarial and Economic Services Division, National Council on Compensation Insurance, Boca Raton, Florida 33487
Email: jpr2718@gmail.com

Jim White
Affiliation: Centre for Mathematics and its Applications, Australian National University, Canberra, ACT 0200, Australia
Email: mathimagics@yahoo.co.uk

DOI: https://doi.org/10.1090/S0025-5718-09-02286-8
Keywords: Pell's equation, nearest square continued fraction
Received by editor(s): July 29, 2008
Received by editor(s) in revised form: March 15, 2009
Published electronically: July 21, 2009
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.