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), 485499
MSC (2000):
Primary 11D09, 11Y50, 11A55, 11Y65
Published electronically:
July 21, 2009
MathSciNet review:
2552236
Fulltext PDF
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, 192930, pp. 225248.
 [2]
A.A.K. Ayyangar, A new continued fraction, Current Sci. 6, June 1938, pp. 602604. 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 (5,92d)
 [4]
Leonard
Eugene Dickson, History of the theory of numbers. Vol. II:
Diophantine analysis, Chelsea Publishing Co., New York, 1966. MR 0245500
(39 #6807b)
 [5]
A.
Hurwitz, Über eine besondere Art der KettenbruchEntwicklung
reeller Grössen, Acta Math. 12 (1889),
no. 1, 367–405 (German). MR
1554778, http://dx.doi.org/10.1007/BF02391885
 [6]
K.R. Matthews and J.P. Robertson, Equality of periodlengths 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. 619652. 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
(16,239e)
 [9]
G.
J. Rieger, Über die mittlere Schrittanzahl bei
Divisionsalgorithmen, Math. Nachr. 82 (1978),
157–180 (German). MR 0480366
(58 #533)
 [10]
Hans
Riesel, On the metric theory of nearest integer continued
fractions, BIT 27 (1987), no. 2, 248–263.
MR 894126
(88k:11048), http://dx.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. 333334.
 [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
(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), no. 145, 369–381. MR 514833
(80e:12003), http://dx.doi.org/10.1090/S00255718197905148331
 [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, 192930, pp. 225248.
 [2]
 A.A.K. Ayyangar, A new continued fraction, Current Sci. 6, June 1938, pp. 602604. Zbl 0019.15504
 [3]
 A.A.K. Ayyangar, Theory of the nearest square continued fraction, J. Mysore Univ. Sect. A. 1, (1941) 97117. 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 KettenbruchEntwicklung reeller Grössen, Acta Math., 12, 1889, pp. 367405. JFM 21.0188.01 MR 1554778
 [6]
 K.R. Matthews and J.P. Robertson, Equality of periodlengths 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. 619652. 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. 157180. MR 0480366 (58:533)
 [10]
 H. Riesel, On the metric theory of nearest integer continued fractions, BIT, 27, 1987, pp. 248263. 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. 333334.
 [12]
 H.C. Williams, Solving the Pell equation, Proc. Millennial Conference on Number Theory, A.K. Peters, 2002, 397435. 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. 369381. 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:
http://dx.doi.org/10.1090/S0025571809022868
PII:
S 00255718(09)022868
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.
