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 $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=\pm 1$, 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.

- 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. - A.A.K. Ayyangar,
*A new continued fraction*, Current Sci.**6**, June 1938, pp. 602-604. Zbl 0019.15504 - Ayyangar Krishnaswami A. A.,
*Theory of the nearest square continued fraction*, J. Mysore Univ. Sect. A**1**(1941), 97–117. MR**9046** - Leonard Eugene Dickson,
*History of the theory of numbers. Vol. II: Diophantine analysis*, Chelsea Publishing Co., New York, 1966. MR**0245500** - A. Hurwitz,
*Über eine besondere Art der Kettenbruch-Entwicklung reeller Grössen*, Acta Math.**12**(1889), no. 1, 367–405 (German). MR**1554778**, DOI https://doi.org/10.1007/BF02391885 - 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). - 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 - Oskar Perron,
*Die Lehre von den Kettenbrüchen. Bd I. Elementare Kettenbrüche*, B. G. Teubner Verlagsgesellschaft, Stuttgart, 1954 (German). 3te Aufl. MR**0064172** - G. J. Rieger,
*Über die mittlere Schrittanzahl bei Divisionsalgorithmen*, Math. Nachr.**82**(1978), 157–180 (German). MR**480366**, DOI https://doi.org/10.1002/mana.19780820115 - Hans Riesel,
*On the metric theory of nearest integer continued fractions*, BIT**27**(1987), no. 2, 248–263. MR**894126**, DOI https://doi.org/10.1007/BF01934188 - D. Shanks,
*Review of UMT File: Two related quadratic surds having continued fractions with exceptionally long periods*, Math. Comp.**28**, 1974, pp. 333-334. - 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** - H. C. Williams and P. A. Buhr,
*Calculation of the regulator of ${\bf Q}(\surd D)$ by use of the nearest integer continued fraction algorithm*, Math. Comp.**33**(1979), no. 145, 369–381. MR**514833**, DOI 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

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.