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 , using the nearest square continued fraction expansion of . The period of the expansion is on average that of the regular continued fraction. We derive similar criteria for the diophantine equation , where . 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.

**[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 by use of the nearest integer continued fraction algorithm*, Math. Comp.**33**, 1979, pp. 369-381. MR**0514833 (80e:12003)**

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.