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 9046
- [4] Leonard Eugene Dickson, History of the theory of numbers. Vol. I: Divisibility and primality., Chelsea Publishing Co., New York, 1966. MR 0245499
- [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 480366, 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.