## Which Diophantine equations can be solved using continued fractions?

Pell equations can be solved using continued fractions. I have heard that some elliptic curves can be "solved" using continued fractions. Is this true?

Which Diophantine equations other than Pell equations can be solved for rational or integer points using continued fractions? If there are others, what are some good references?

Edit:

Professor Elkies has given an excellent response as to the role of continued fractions in solving general Diophantine equations including elliptic curves. What are some other methods to solve the Diophantine equations $$X^2 - \Delta Y^2 = 4 Z^3$$ and $$18 x y + x^2 y^2 - 4 x^3 - 4 y^3 - 27 = D z^2 ?$$

-
 Samuel, could you be a little more specific about your comment about solving $x^2 - D y^2 = 4 z^3,$ especially why you are not satisfied with your parametrized solution? I printed out your paper with Franz, "Arithmetic of Pell Surfaces," where I think equation (1.1) with $n=3$ is what you are discussing below. Also Buell's book, especially pages 147-157, discussing Nagell 1922 and Yamamoto 1970. – Will Jagy Oct 17 2011 at 0:03 Thank you Dr. Jagy for comment, interest in the question, and for your help with question 71727 ! I've also seen that you're interested in ternary quadratic forms, which I would like to learn about too. My response will require quite the maximum characters, so I'll stop chatting and get to it. – Samuel Hambleton Oct 19 2011 at 2:13 Let $\Delta = 229$ and $K = \mathbb{Q}(\sqrt{\Delta })$. Then $\text{Cl}^+(K)[3] \simeq (\mathbb{Z}/ \3 )$. Using the "parametrization" in Mathematica5, d = 229; S = Union[DeleteCases[Partition[Flatten[Table[P = {(t^3 + 3 d t u^2)/4,(3 t^2 u + d u^3)/4,(t^2 - d u^2)/4};If[IntegerQ[P[[1]]] && IntegerQ[P[[2]]] && IntegerQ[P[[3]]] && GCD[P[[1]], P[[3]]] == 1, P, {w, w, w}], {t, -100, 100}, {u, -100, 100}]], 3], {w, w, w}]]; gives the Points of the "Pell surface" $x^2 - d y^2 = 4 z^3$ from the "parametrization". On the other hand, a brute force search for points satisfying this Eqn. can be ... – Samuel Hambleton Oct 19 2011 at 2:27 ... done as: T = Union[DeleteCases[Partition[Flatten[Table[If[IntegerQ[Sqrt[d y^2 + 4 z^3]] && GCD[Sqrt[d y^2 + 4 z^3], z] == 1, {Sqrt[d y^2 + 4 z^3], y, z}, {w, w, w}], {y, -100, 100}, {z, -100, 100}]], 3], {w, w, w}]]; There are points of the set $T$ not in $S$, for example : $(11, 1, 3)$. The other form of the Pell surface is $B^2 + B C - 57 C^2 = A^3$. With point $(11, 1, 3)$ corresponding to $(A, B, C) = (3, 5, 1)$, which should map to the ideal $(3, 2 + (1 + \sqrt{\Delta })/2)$. I suspect that the "parametrization" leads to principal ideals. – Samuel Hambleton Oct 19 2011 at 2:39 The points should read $(11, 1, -3)$, $(-3, 5, 1)$, and ideal $(-3, 2 + (1 + \sqrt{229})/2)$. I would like to know of more methods for solving Diophantine equations, especially surfaces. Professor Elkies'methods look promising. Joro's question 70913, and particularly Schoof's article linked there shows that there may be some good reasons to want an easy method for finding non-principal ideals. I am particularly keen to learn methods for solving $18 x y +x^2 y^2 -4 x^3 -4 y^3 -27 = D z^2$. – Samuel Hambleton Oct 19 2011 at 2:50
show 2 more comments

## 6 Answers

[edited to insert paragraph on Cornacchia and point-counting]

Continued fractions, or (more-or-less) equivalently the Euclidean algorithm, can be used to find small integer solutions of linear Diophantine equations $ax+by=c$, and integer solutions of quadratic equations such as $x^2-Dy^2=\pm1$ ("Pell"). Continued fractions in themselves won't find rational points on elliptic curves, but there's a technique using Heegner points that calculates a close real approximation to a rational point, which is then recovered from a continued fraction — this is possible because the recovery problem amounts to finding a small integer solution of a linear Diophantine equation. My paper

Noam D. Elkies: Heegner point computations, Lecture Notes in Computer Science 877 (proceedings of ANTS-1, 5/94; L.M. Adleman and M.-D. Huang, eds.), 122-133.

might have been the first to describe this approach.

Another application of continued fractions is Cornacchia's algorithm to solve $x^2+Dy^2=m$ for large $m>0$ coprime to $D$, given $x/y \bmod m$ which is a square root of $-D \bmod m$. This has an application to counting points on elliptic curves $E\bmod p$ for $E$ such as $y^2 = x^3 + b$ or $y^2 = x^3 + ax$ for which the CM field ${\bf Q}(\sqrt{-D})$ is known: the count (including the point at infinity) is $p+1-t$ where $t^2+Du^2=4p$ for some integers $t$ and $u$, and this determines $t$ up to an ambiguity of at most $6$ possibilities that in practice is readily resolved. The necessary square root mod $p$ is readily found in random polynomial time, though it is a persistent embarrassment that we cannot extract square roots modulo a large prime in deterministic polynomial time without assuming something like the extended Riemann hypothesis. Indeed the application that Schoof gave to motivate his polynomial-time algorithm to compute $t$ for any elliptic curve mod $p$ was to recover a square root of $-D \bmod p$ for small $D$ ! (Though this would never be done in practice because the exponent in Schoof's algorithm is much larger than for the randomized algorithm.) The reference for Schoof's paper is

René Schoof: Elliptic Curves over Finite Fields and the Computation of Square Roots $\bmod p$, Math. Comp. 44 (#170, April 1985), 483-494.

A natural generalization of the Euclidean algorithm to higher dimensions is the LLL algorithm and other techniques for lattice basis reduction (LBR), which have found various other Diophantine uses, including some other techniques for finding rational points on elliptic curves; another of my papers describes some of these Diophantine applications of LBR.

-
 Awesome. Thank you Professor Elkies. That should get me started. I can't remember who told me about continued fractions with respect to elliptic curves but I thought they mentioned Artin. I'm not sure. – Samuel Hambleton Oct 13 2011 at 2:51 This is a slightly different topic now but I've seen a cool paper of Professor Elkies' : "Pythagorean triples and Hilbert's Theorem 90", which I tried to apply to $x^2 - D y^2 = 4 z^3$. It partially worked but I couldn't seem to get the points I was interested in, and so I was wondering about continued fractions. – Samuel Hambleton Oct 13 2011 at 3:40 @R.Thornburn: 1a) You're welcome! 1b) Perhaps Artin was thinking about point-*counting* on elliptic curves modulo a prime; see the paragraph I inserted. 2) Looks like this equation $x^2-Dy^2=4z^3$ will involve the $3$-torsion in the class group of ${\bf Z}[(D+\sqrt{D})/2]$, which may be accessible via the continued fraction for $(D+\sqrt{D})/2$ but I suspect that this is not the most efficient method for large $D$. – Noam D. Elkies Oct 14 2011 at 20:02 With a change of variables, one can handle all of the equations $A x^2 + B x y + C y^2 + D x + E y + F =0$ in much the same way as Pell's Equation. – Kevin O'Bryant Oct 14 2011 at 23:37 Thank you both very much, and sorry about my identity crisis. I initially wanted to vote the answer to Question 70913 to a non-negative number. I don't want to be deceitful. The incomplete "parametrization" I found for $x^2 - D y^2 = 4 z^3$ is $((t^3+3 D t u^2)/4, (3 t^2 u + D u^3)/4 , (t^2 - D u^2)/4)$ but I can't seem to get elements of to narrow class group of exact order $3$ with this "parametrization". I am also interested in solving $18 x y + x^2 y^2 - 4 x^3 - 4 y^3 - 27 = D z^2$. – Samuel Hambleton Oct 16 2011 at 4:32

Hello, I want to necromance this thread back to life because I was working on a very similar question (and therefore it would only make sense to post it here).

If I have the diophantine equation

X^2 - Y^2 = C

Assuming we have already proven that this equation has solutions and a finite number of them, how do I efficiently find the smallest value of X and Y, both greater than zero that satisfy this equation.

ex:

x^2 - y^2 = 2684

A solution to this equation is x = 672, y = 670. But the smallest solution to this equation is x = 72, y = 50. If i'm most interested in finding the latter how would I go about doing so without just trial and error. Can continued fractions play a role here and if so then how? Can secant and tangent lines to the graph of X^2 - Y^2 = C play a role in finding rational points? If so then how? Thank you very much for your time!

-
If you want to ask a new question that may be related to an existing one, better to just ask the question and give the reference. In the present case, though, your question seems to be almost equivalent to a question that was already asked here earlier this month (#98637: "find the minimum difference between the factors of a number"), and I think was also seen here before that. So you might just consult that thread. – Noam D. Elkies Jun 20 at 0:58
Thank you for your response! I did look at the thread and our threads are quite different. My question is basically attempting to maximize the value of abs(x - y) whereas that thread was concerned with minimizing the value. In other words the asker on the other post would be most interested in what I am least interested in. Additionally I am interested in the absolute minimal solution to x^2 - y^2 = 2684 (where x and y > 0) regardless of whether x and y do multiply out to create 2684. That being said would you suggest that I post this question in altogether new thread or keep it here for now? – Sid Jun 20 at 1:18
Since $X^2 - Y^2 = (X+Y) (X-Y)$, you can take $(x,y) = (X+Y,X-Y)$. Then $xy=C$, and $|x-y|=2Y$, so the questions are almost the same except that we must impose the condition $x \equiv y \bmod 2$ to ensure the integrality of $X$ and $Y$ [which are $(x\pm y)/2$]. – Noam D. Elkies Jun 20 at 2:16

I was about to mention H J S Smith's algorithm for finding integer solutions to $x^2 + y^2 = p$ for $p \equiv 1$ mod 4; but this is referred to in a related thread at http://mathoverflow.net/questions/49866/applications-of-finite-continued-fractions

(Apologies if that thread is easily found from this one; but I wouldn't have noticed it without doing a Google search, and perhaps some other readers are equally inexperienced in StackOverflow ways or unobservant!)

Also, what about higher-dimensional continued fractions, expressed as matrix recurrence relations? I seem to recall that these can be used to find rational solutions of equations involving some kinds of cubic forms.

-

In 1993, Tzanakis ( http://matwbn.icm.edu.pl/ksiazki/aa/aa64/aa6435.pdf ) showed that solving a quartic Thue equation, which correponding quartic field is the compositum of two real quadratic fields, reduces to solving a system of Pellian equations.

Even if the system of Pellian equations cannot be solved completely, the information on solutions obtained from the theory of continued fractions and Diophantine approximations might be sufficient to show that the Thue equation (or Thue inequality) has no solutions or has only trivial solutions. For that purpose, very useful tool is Worley's result characterizing all rational approximations satifying $|\alpha - \frac{p}{q}| < \frac{c}{q^2}$ in terms of convergents of continued fraction of $\alpha$. You may consult the paper "Solving a family of quartic Thue inequalities using continued fractions" ( http://web.math.pmf.unizg.hr/~duje/pdf/dij.pdf ) and the references given there.

-

I should have stuck with your preferred notation, as in your $B^2 + B C - 57 C^2 = A^3$ in a comment. So the form of interest will be $x^2 + x y - 57 y^2.$The other classes with this discriminant of indefinite integral binary quadratic forms would then be given by $3 x^2 \pm xy - 19 y^2.$

Therefore, take $$\phi(x,y) = x^2 + x y - 57 y^2.$$ The identity you need to deal with your $A= \pm 3$ is $$\phi( 15 x^3 - 99 x^2 y + 252 x y^2 - 181 y^3 , \; 2 x^3 - 15 x^2 y + 33 x y^2 - 28 y^3 ) \; = \; ( 3 x^2 + xy - 19 y^2 )^3$$

This leads most directly to $\phi(15,2) = 27.$ Using $3 x^2 + x y - 19 y^2 = -3$ when $x=7, y=3,$ this leads directly to $\phi(1581, -196) = -27.$

However, we have an automorph of $\phi,$ $$W \; = \; \left( \begin{array}{rr} 106 & 855 \\ 15 & 121 \end{array} \right) ,$$ and $W \cdot (1581,-196)^T = (6, -1)^T,$ so $\phi(6,-1) = -27.$

Finally, any principal form of odd discriminant, call it $x^2 + x y + k y^2,$ (you have $k=-57$) has the improper automorph $$Z \; = \; \left( \begin{array}{rr} 1 & 1 \\ 0 & -1 \end{array} \right) ,$$ while $Z \cdot (6,-1)^T = (5, 1)^T,$ so $\phi(5,1) = -27.$

EDIT: a single formula cannot be visually obvious for all desired outcomes. There are an infinite number of integral solutions to $3 x^2 + x y - 19y^2 = -3.$ It is an excellent bet that one of these leads, through the identity I give, to at least one of the desired $\phi(5,1) = -27$ or $\phi(6,-1) = -27,$ but not necessarily both, largely because $3 x^2 + x y - 19y^2$ and $3 x^2 - x y - 19y^2$ are not properly equivalent. Worth investigating, I should think.

-
 I think Dr. Jagy is saying that one can obtain all solutions of X^2 - D y^2 = 4 Z^3 by using representative binary quadratic forms of each of the classes of forms. For D = 229, there are three. This is correct, we can solve X^2 - D y^2 = 4 Z^3 by looking at classes of forms. Part of the proof is that the map from points of ( X^2 - D y^2 = 4 Z^3 ) to Cl^+(D)[3] is surjective. I am curious to know whether it can get computationally easier than this. Possibly not? – Samuel Hambleton Oct 23 2011 at 6:47

For your sample problem, I get two flavors of identity, principal and non-principal.

For discriminant 229, I take the identity form as $$f(x,y) = x^2 + 15 x y - y^2.$$ One of your families is $$f(x^3 + 3 x y^2 + 5 y^3, \; 3 x^2 y + 45 x y^2 + 226 y^3 ) \; = \; f^3(x,y).$$ As an automorph of $f$ is $$\left( \begin{array}{rr} 1 & 15 \\ 15 & 226 \end{array} \right) ,$$ from the column vector $(1,0)^T$ we get another representation of 1 as $(1,15)^T.$ So that is one type of thing.

For the other two classes, take $$g(x,y) = 3 x^2 + 13 x y - 5 y^2.$$ A second family is $$f( x^3 + 12 x^2 y + 57 x y^2 + 89 y^3, \; 2 x^3 - 3 x^2 y - 3 x y^2 - 6 y^3 ) \; = \; g^3(x,y).$$
  The following cycles of reduced forms are as in Buell's book, pages 21-30.

=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$./indefCycle Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2 1 15 -1 0 form 1 15 -1 delta -15 1 form -1 15 1 delta 15 2 form 1 15 -1 minimum was 1rep 1 0 disc 229 dSqrt 15.13274595 M_Ratio 229 Automorph, written on right of Gram matrix: -1 -15 -15 -226 Trace: -227 gcd(a21, a22 - a11, a12) : 15 ========================================= ========================================= jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle
Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2
3 13 -5

0  form   3 13 -5   delta  -2
1  form   -5 7 9   delta  1
2  form   9 11 -3   delta  -4
3  form   -3 13 5   delta  2
4  form   5 7 -9   delta  -1
5  form   -9 11 3   delta  4
6  form   3 13 -5
minimum was   3rep 1 0 disc   229 dSqrt 15.13274595  M_Ratio  25.44444
Automorph, written on right of Gram matrix:
-16  -75
-45  -211
Trace:  -227   gcd(a21, a22 - a11, a12) : 15
=========================================

-
 Thanks. Are you saying that the binary quadratic form $3 x^2 + 13 x y -5 y^2$ comes from the parametrization? From Yamamoto's work, which appears in Buell's book, the binary quadratic form $(z, x, z^2)$ is discussed, where $x^2 - \Delta y^2 = 4 z^3$ and $gcd(x, z) = 1$. Franz Lemmermeyer and I looked at $z T^2 + x T U + z^2 U^2 = \Delta y^2$. If rel. prime integers $T, U$ exist satisfying this, then $(z, x, z^2)$ is principle. I think there should be polynomials $T(t,u)$ and $U(t, u)$ : $$((t^2 - Δ u^2)/4)T^2 + ((t^3 + 3 Δ t u^2)/4) T U + ((t^2 - Δ u^2)/4)^2U^2 = Δ ((3t^2 u + Δ u^3)/4)^2 ,$$ – Samuel Hambleton Oct 19 2011 at 10:57 If there are such polynomials $T(t, u)$ and $U(t, u)$, then points from the "parametrization" yield principal forms and principal ideals. I haven't found any such polynomials. – Samuel Hambleton Oct 19 2011 at 11:02