Methods for solving Pell's equation? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T15:01:35Z http://mathoverflow.net/feeds/question/48251 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/48251/methods-for-solving-pells-equation Methods for solving Pell's equation? Andrey 2010-12-04T05:35:39Z 2011-10-07T05:42:53Z <p>It is known that the minimum solution of Pell's equation $x^2-dy^2=\pm1$ can be found from the continued fraction expansion of $\sqrt d$. Are there other methods for finding the minimum (or any other) solutions? </p> http://mathoverflow.net/questions/48251/methods-for-solving-pells-equation/48252#48252 Answer by felix for Methods for solving Pell's equation? felix 2010-12-04T05:55:27Z 2010-12-04T05:55:27Z <p>Any algorithm for computing fundamental units of a real quadratic number field $\mathbb{Q}(\sqrt{D})$ can be used for solving Pell's equation. (You might have to do a bit of work to convert the result, but that can be done in polynomial time...)</p> <p>See for example M. Jacobson, H. Williams: Solving the Pell Equation. Springer, 2009.</p> http://mathoverflow.net/questions/48251/methods-for-solving-pells-equation/48253#48253 Answer by Will Jagy for Methods for solving Pell's equation? Will Jagy 2010-12-04T05:57:59Z 2010-12-04T05:57:59Z <p>It is really the same method, but see my answer at</p> <p><a href="http://mathoverflow.net/questions/22811/upper-bound-of-period-length-of-continued-fraction-representation-of-very-composi/23014#23014" rel="nofollow">http://mathoverflow.net/questions/22811/upper-bound-of-period-length-of-continued-fraction-representation-of-very-composi/23014#23014</a> </p> <p>The one thing I would add here is that, if the main concern is the length of the period, the continued fraction digits are the absolute values of my $\delta$'s, so sometimes the continued fraction period is half the cycle length.</p> http://mathoverflow.net/questions/48251/methods-for-solving-pells-equation/48254#48254 Answer by David Eppstein for Methods for solving Pell's equation? David Eppstein 2010-12-04T05:59:46Z 2010-12-04T05:59:46Z <p>Another nice reference on this problem (and non-CF methods to solve it) is Lenstra's 2002 notices survey, "<a href="http://www.ams.org/notices/200202/fea-lenstra.pdf" rel="nofollow">Solving the Pell Equation</a>".</p> http://mathoverflow.net/questions/48251/methods-for-solving-pells-equation/48270#48270 Answer by Franz Lemmermeyer for Methods for solving Pell's equation? Franz Lemmermeyer 2010-12-04T11:25:08Z 2010-12-04T11:57:47Z <p>The basic and classical methods, apart from brute force, are</p> <ul> <li><p>continued fraction expansions (regular, nearest integer, etc.) or, equivalently, some form of reduction theory for indefinite binary quadratic forms;</p></li> <li><p>computing many elements of small norm in a quadratic number field, which often is a lot more effective; the technique used here is also used for factoring integers.</p></li> </ul> <p>For a detailed algorithmic description see Jacobson &amp; Williams (Solving the Pell Equation) or Buchmann &amp; Vollmer (Binary Quadratic Forms). </p> <p>In addition, you can compute a power of the fundamental unit from the class number formulas, which essentially consists in taking norms of suitable cyclotomic units. Kronecker has shown how to solve the Pell equation using elliptic and modular functions, and Girstmair (Kronecker's solution of the Pell equation on a computer {Kroneckers L&ouml;sung der Pellschen Gleichung auf dem Computer], Math. Semesterber. 53, 45-64 (2006)) has shown that it can be made to work in practice.</p> <p>You can also imitate the theory of descent on elliptic curves; I have sketched connections with classical tricks in some preprints on <a href="http://www.rzuser.uni-heidelberg.de/~hb3/publ-new.html" rel="nofollow">higher descent on Pell conics</a>.</p> http://mathoverflow.net/questions/48251/methods-for-solving-pells-equation/77423#77423 Answer by Samuel Hambleton for Methods for solving Pell's equation? Samuel Hambleton 2011-10-07T05:37:40Z 2011-10-07T05:42:53Z <p>Just to add another method to the collection: Let $\Delta = \sigma + 4 m$, be the fundamental discriminant of a quadratic field, where $\sigma \in { 0, 1 }$. Let $(x / z , y / z)$ be a rational solution of the Pell conic $x^2 + \sigma x y - m y^2 = 1$, with $\text{gcd}(x, y) = 1$, and let $\beta \equiv x \cdot y^{-1} \pmod{z}$. Assume that $q_1 = (t_1, u_1)$, $q_2 = (t_2, u_2)$ satisfy $z t^2 + (2 \beta + \sigma ) t u + \frac{\beta^2 + \sigma \beta - m}{z} u^2 = 1$ in rational integers, then $\nu (q_2 , q_1 ) =$ I am trying to write a matrix times a vector: $(z t_1 + (\beta + \sigma ) u_1, \beta t_1 + \frac{\beta^2 + \sigma \beta - m}{z} u_1,- u_1,t_1 ) (t_2, u_2)$ satisfies the Pell conic in rational integers. I learned about the map $\nu$ from Franz Lemmermeyer, his articles and book `Binary quadratic forms'. There is a bijection between the integer points $(t, u)$ and the primitive integer points $(T, U)$ of $z T^2 + (2 x + \sigma y) T U + z U^2 = y^2$. Given a primitive integer point $(T, U)$, we also have a primitive integer point $(U, T)$. Using this bijection, given an integer point $(t_1, u_1)$, we obtain another point $(t_2, u_2) = (\kappa t_1 + \kappa' u_1, y t_1 - \kappa u_1)$, where $\kappa = \frac{x - \beta y}{z}$, and $\kappa' = \frac{(2 \beta + \sigma ) x - (\beta^2 + m ) y}{z^2}$. The points $(t_1, u_1), (t_2, u_2)$ are used with $\nu$ to obtain an integer point of the Pell conic. In particular, letting $\gamma = \frac{\beta^2 + \sigma \beta - m}{z}$, $( x t^2 + (z \kappa' + \sigma \kappa + y \gamma ) t u + ((\beta + \sigma ) \kappa' - \kappa \gamma ) u^2, y t^2 - 2 \kappa t u - \kappa' u^2 )$. One must check that $T \not= U$, equivalently that $y t \not= (\kappa + 1) u$, for otherwise this method will not work. This follows from "Arithmetic of Pell surfaces", Acta Arith., 146, (2011), no. 1, 1--12.</p>