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

DOI:
https://doi.org/10.1090/S0025-5718-09-02286-8

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]**Ayyangar Krishnaswami A. A.,*Theory of the nearest square continued fraction*, J. Mysore Univ. Sect. A.**1**(1941), 97–117. MR**0009046****[4]**Leonard Eugene Dickson,*History of the theory of numbers. Vol. I: Divisibility and primality.*, Chelsea Publishing Co., New York, 1966. MR**0245499**

Leonard Eugene Dickson,*History of the theory of numbers. Vol. II: Diophantine analysis*, Chelsea Publishing Co., New York, 1966. MR**0245500**

Leonard Eugene Dickson,*History of the theory of numbers. Vol. III: Quadratic and higher forms.*, With a chapter on the class number by G. H. Cresse, Chelsea Publishing Co., New York, 1966. MR**0245501****[5]**A. Hurwitz,*Über eine besondere Art der Kettenbruch-Entwicklung reeller Grössen*, Acta Math.**12**(1889), no. 1, 367–405 (German). MR**1554778**, https://doi.org/10.1007/BF02391885**[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]**Oskar Perron,*Die Lehre von den Kettenbrüchen. Bd I. Elementare Kettenbrüche*, B. G. Teubner Verlagsgesellschaft, Stuttgart, 1954 (German). 3te Aufl. MR**0064172****[9]**G. J. Rieger,*Über die mittlere Schrittanzahl bei Divisionsalgorithmen*, Math. Nachr.**82**(1978), 157–180 (German). MR**0480366**, https://doi.org/10.1002/mana.19780820115**[10]**Hans Riesel,*On the metric theory of nearest integer continued fractions*, BIT**27**(1987), no. 2, 248–263. MR**894126**, https://doi.org/10.1007/BF01934188**[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*, Number theory for the millennium, III (Urbana, IL, 2000) A K Peters, Natick, MA, 2002, pp. 397–435. MR**1956288****[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), no. 145, 369–381. MR**514833**, https://doi.org/10.1090/S0025-5718-1979-0514833-1

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.