Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

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

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


References [Enhancements On Off] (What's this?)


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/S0025-5718-09-02286-8
PII: S 0025-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.