Midpoint criteria for solving pell's equation using the nearest square continued fraction

Keith Matthews; John Robertson; Jim White

doi:10.1090/S0025-5718-09-02286-8

Midpoint criteria for solving pell's equation using the nearest square continued fraction

Keith Matthews^*, John Robertson, Jim White

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

We derive midpoint criteria for solving Pell's equation x²-Dy² = ±1, using the nearest square continued fraction expansion of √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² - xy - (D-1) 4 y² = ±1, where D ≡ 1 (mod 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.

Original language	English
Pages (from-to)	485-499
Number of pages	15
Journal	Mathematics of Computation
Volume	79
Issue number	269
DOIs	https://doi.org/10.1090/S0025-5718-09-02286-8
Publication status	Published - 2010

Access to Document

10.1090/S0025-5718-09-02286-8

Cite this

@article{5a74fc5fee3247ce8d2966012bd77eb2,

title = "Midpoint criteria for solving pell's equation using the nearest square continued fraction",

abstract = "We derive midpoint criteria for solving Pell's equation x2-Dy2 = ±1, using the nearest square continued fraction expansion of √D. The period of the expansion is on average 70% that of the regular continued fraction. We derive similar criteria for the diophantine equation x2 - xy - (D-1) 4 y2 = ±1, where D ≡ 1 (mod 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.",

keywords = "Nearest square continued fraction, Pell's equation",

author = "Keith Matthews and John Robertson and Jim White",

year = "2010",

doi = "10.1090/S0025-5718-09-02286-8",

language = "English",

volume = "79",

pages = "485--499",

journal = "Mathematics of Computation",

issn = "0025-5718",

publisher = "American Mathematical Society",

number = "269",

}

TY - JOUR

T1 - Midpoint criteria for solving pell's equation using the nearest square continued fraction

AU - Matthews, Keith

AU - Robertson, John

AU - White, Jim

PY - 2010

Y1 - 2010

N2 - We derive midpoint criteria for solving Pell's equation x2-Dy2 = ±1, using the nearest square continued fraction expansion of √D. The period of the expansion is on average 70% that of the regular continued fraction. We derive similar criteria for the diophantine equation x2 - xy - (D-1) 4 y2 = ±1, where D ≡ 1 (mod 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.

AB - We derive midpoint criteria for solving Pell's equation x2-Dy2 = ±1, using the nearest square continued fraction expansion of √D. The period of the expansion is on average 70% that of the regular continued fraction. We derive similar criteria for the diophantine equation x2 - xy - (D-1) 4 y2 = ±1, where D ≡ 1 (mod 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.

KW - Nearest square continued fraction

KW - Pell's equation

UR - http://www.scopus.com/inward/record.url?scp=77952807032&partnerID=8YFLogxK

U2 - 10.1090/S0025-5718-09-02286-8

DO - 10.1090/S0025-5718-09-02286-8

M3 - Article

SN - 0025-5718

VL - 79

SP - 485

EP - 499

JO - Mathematics of Computation

JF - Mathematics of Computation

IS - 269

ER -

Midpoint criteria for solving pell's equation using the nearest square continued fraction

Abstract

Access to Document

Other files and links

Fingerprint

Cite this