Editing Pell's equation (section)

===Fundamental solution via continued fractions===

Let <math>h_i/k_i</math> denote the unique sequence of [[Convergent (continued fraction)|convergents]] of the [[continued fraction|regular continued fraction]] for <math>\sqrt{n}</math>. Then the pair of positive integers <math>(x_1, y_1)</math> solving Pell's equation and minimizing ''x'' satisfies ''x''<sub>1</sub> = ''h<sub>i</sub>'' and ''y''<sub>1</sub> = ''k<sub>i</sub>'' for some ''i''. This pair is called the ''fundamental solution''. The sequence of integers <math>[a_0; a_1,a_2,\ldots]</math> in the regular continued fraction of <math>\sqrt{n}</math> is always eventually periodic. It can be written in the form <math>\left[\lfloor\sqrt{n}\rfloor;\;\overline{a_1,a_2,\ldots,a_{r-1}, 2\lfloor\sqrt{n}\rfloor}\right]</math>, where <math>\lfloor\, \cdot\, \rfloor</math> denotes integer floor, and the sequence <math>a_1,a_2,\ldots,a_{r-1}, 2\lfloor\sqrt{n}\rfloor</math> repeats infinitely. Moreover, the tuple <math>(a_1,a_2,\ldots,a_{r-1})</math> is [[palindrome | palindromic]], the same left-to-right or right-to-left.<ref name="titu" /> 

The fundamental solution is
<math display="block">(x_1, y_1)=\begin{cases} (h_{r-1}, k_{r-1}),&\text{ for }r\text{ even}\\
(h_{2r-1},k_{2r-1}),&\text{ for }r\text{ odd}\end{cases}</math>

The computation time for finding the fundamental solution using the continued fraction method, with the aid of the [[Schönhage–Strassen algorithm]] for fast integer multiplication, is within a logarithmic factor of the solution size, the number of digits in the pair <math>(x_1, y_1)</math>. However, this is not a [[polynomial-time algorithm]] because the number of digits in the solution may be as large as {{radic|''n''}}, far larger than a polynomial in the number of digits in the input value ''n''.<ref name=":0">{{Citation |last=Lenstra |first=H. W. Jr. |title=Solving the Pell Equation |url=https://www.ams.org/notices/200202/fea-lenstra.pdf |journal=[[Notices of the American Mathematical Society]] |volume=49 |issue=2 |pages=182–192 |year=2002 |mr=1875156 |author-link=Hendrik Lenstra}}.</ref>