# Generate solutions of Quadratic Diophantine Equation

Recently I've asked a question for how to solve Quadratic Diophantine Equation and I got one interesting answer. Link to question: The quadratic diophantine $k^2 - 1 = 5(m^2 - 1)$

$$x_n + y_n \sqrt{5} = \left(x_{n-1} + y_{n-1} \sqrt{5}\right)\left(\frac {3 + \sqrt{5}}{2}\right)^n$$

Actually it worked for my equation, which was: $x^2 - 5y^2 = -4$

I found the fundamental solution and it's $(x,y) = (1,1)$ and using the form from above i get:

$$n = 1; (x,y) = (4,2)$$ $$n = 2; (x,y) = (11,5)$$ $$n = 4; (x,y) = (76,34)\ and\ so\ on$$

And indeed those pairs are solutions for my equation. (I excluded every non-integer numbers, because I'm only interested in integers)

But I'm experiencing problems with the following equation: $x^2 - 17y^2 = 13$

Fundamental solution is (9,2) and using the above form I get:

$$n = 3; (x,y) = (121, 54)$$

And if I check this pair isn't solution to the equation. Where am I wrong?

• What did you use in place of $\sqrt{5}$ and (more importantly) $(3+\sqrt{5})/2$? – Erick Wong Mar 27 '13 at 0:47
• I used the same number, because they are constant and only $a_n$ and $b_n$ changes, at least the answer states so. – Stefan4024 Mar 27 '13 at 0:55
• It's unreasonable to expect a method that is specifically designed to keep $x^2-5y^2$ constant to simultaneously hold $x^2-17y^2$ constant. Do you think it's coincidence that there was a $5$ inside the square root and a $5$ in $x^2-5y^2$? – Erick Wong Mar 27 '13 at 2:47

The "topograph" for $x^2 - 13 y^2$ is definitely more complicated than the previous ones, because the continued fraction for $\sqrt {13}$ has period 5, your two previous examples had period 1. Confirming the "automorph" matrix, which just preserves the quadratic form:

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

gp-pari
?
?
? form = [ 1,0; 0,-13]
%1 =
[1 0]

[0 -13]

?
? a = [649, 2340; 180, 649]
%2 =
[649 2340]

[180 649]

?
? atranspose = mattranspose(a)
%3 =
[649 180]

[2340 649]

?
?  atranspose  * form * a
%5 =
[1 0]

[0 -13]


=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

The pairs of numbers in green are vectors in the plane. Two basic properties. First, each shows its value for $x^2 - 13 y^2.$ For example, in the first occurrence of 4, we see the (column) vector $(11,3),$ and we can easily confirm that $11^2 - 13 \cdot 3^2 = 4.$ Next, around any point where three purple line segments meet (even if two are parallel), one of the three green vectors is the sum of the other two. For example, $$(4,1) + (7,2) = (11,3).$$ As long as we just continue to the right, we can continue getting all positive entries in green.

Oh: you said you can do continued fractions. It happens that you can find all representations of 4 and 1 using the continued fraction of $\sqrt {13},$ so you can confirm a good deal of the Conway diagram, the vectors in green, whatever.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

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 0 -13 0 form 1 0 -13 delta 0 1 form -13 0 1 delta 3 2 form 1 6 -4 -1 -3 0 -1 To Return -1 3 0 -1 0 form 1 6 -4 delta -1 1 form -4 2 3 delta 1 2 form 3 4 -3 delta -1 3 form -3 2 4 delta 1 4 form 4 6 -1 delta -6 5 form -1 6 4 delta 1 6 form 4 2 -3 delta -1 7 form -3 4 3 delta 1 8 form 3 2 -4 delta -1 9 form -4 6 1 delta 6 10 form 1 6 -4  =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= • Great work man. It'll helped me a lot and finally I understand. I've tried with$x^2 - 15y^2 = -15$and the automorph is $$A = \left( \begin{array}{cc} 4 & 15 \\ 1 & 4 \end{array} \right).$$ – Stefan4024 Mar 29 '13 at 1:09 • Oh: I made a mistake in the previous calculations: it must be because I stayed up late at that moment.And thanks for this answer: it is clear and instructive. And might I ask, where I could find the exposition of this "topograph" in connection with the reduced forms of Lagrange? And what do the reduced forms have to do with continued fractions? Thanks in any case in advance? P.S. It was an exciting moment when I realised that this graph could produce an effective algorithm for dealing with quadratic forms: I thought of this subject as quite difficult, ... – awllower Mar 29 '13 at 1:38 • Good. Notice that, this time, there is no solution to$x^2 - 15 y^2 = -1$or$x^2 - 15 y^2 = -4.$In Conway's approach, this is shown by the Climbing Lemma, which says that, as you draw in more edges and openings away from the river, the values on each side of the river keep a consistent$\pm$sign but increase in absolute value. I drew in just a litlle such extra in the$x^2 - 17 y^2$drawing. – Will Jagy Mar 29 '13 at 1:38 • @awllower, I give a pretty good summary of Buell's discussion of the cycle method at mathoverflow.net/questions/22811/… – Will Jagy Mar 29 '13 at 1:57 • @Stefan4024, I posted a new answer for$x^2 - 12 y^2$including the target value 13. In general, we need to draw in extra layers away from the river. See The Climbing Lemma in Conway, book page 11, and the diagram with extra layers on book page 22. Of course, the diagram gets a little cramped for space. – Will Jagy Mar 29 '13 at 19:43 Stefan, you generally need to add more layers away from the river, and that is the case for$x^2 - 12 y^2$and the target number 13. In this expanded diagram, you see how moving away from the river increases the absolute value of the purple numbers. However, none possessing a primitive representation ($\gcd(x,y)=1$) is missed. Here the two starting vectors for 13 are$(5,1)$and$(11,3).$=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= • Thanks mate. Would you like to put a solution an equation of the type$ax^2 - bxy - cy^2 = d$, where a,b,c,d are not 0, becuse I have problem with this one. – Stefan4024 Mar 29 '13 at 23:55 This method is in Conway's book. Automorphs are treated in the most detail in Buell's book Binary Quadratic Forms. Also in A Course in Number Theory by H. E. Rose. Same method, less color. The automorph$A$is at the top, as $$A = \left( \begin{array}{cc} 33 & 136 \\ 8 & 33 \end{array} \right).$$ You can check: $$\left( \begin{array}{cc} 33 & 8 \\ 136 & 33 \end{array} \right) \left( \begin{array}{cc} 1 & 0 \\ 0 & -17 \end{array} \right) \left( \begin{array}{cc} 33 & 136 \\ 8 & 33 \end{array} \right) = \left( \begin{array}{cc} 1 & 0 \\ 0 & -17 \end{array} \right).$$ • It may be only me and the methods I'm used to, but unless somebody explains to me what you wrote up there I would understand almost nothing...beginning by the term "automorph" which is known to me only from group theory. – DonAntonio Mar 27 '13 at 2:55 • @Stefan4024, it is time to ask how old you are and what background in mathematics you might have. Also, why you show no interest in reading the references I have provided. The instructions for the diagram above are about 30 pages in Conway, I am not going to type that out when you can read it yourself. – Will Jagy Mar 27 '13 at 19:18 • Thanks for providing the pdf: I am reading it through now. It seems to be involved with graph theory in some way. In any case, thanks again for your munificence. – awllower Mar 27 '13 at 19:40 • I've read the book more carefully and it's clearer to me. So I decide to solve one equation by myself. But then I have problem. The equation is$x^2 - 13y^2 = 4; (x,y) = (11,3)$. I've started well and I think i haven't made a mistake, but I don't know how to continue. And one more question how did you get those numbers in the parethesis, i've never seen such number in the book you gave me. Here's what i've done: img585.imageshack.us/img585/6329/quadraticform.jpg – Stefan4024 Mar 28 '13 at 13:04 • @Stefan4024 I am not sure what you are doing: I would like to discuss with you this topic, and here is what I have done, according to which the automorphy should be$A=\begin{pmatrix}649&1691\\180&469\end{pmatrix}$. Regards. P.S. Forgive the poor photo: I do not have good skill, neither in photo-taking, nor in uploading photos. – awllower Mar 28 '13 at 19:34 The generating unit is now the square of$4+\sqrt{17}$. Apart from that, nothing much changes. • Can you give me an formula to get the generating unit for every quadratic diophantine equation. And also should I use square root of 5 in this$(x_{n−1}+y_{n−1}\sqrt{5})$– Stefan4024 Mar 27 '13 at 10:45 • Explain it how you get$(3+\sqrt{13})/2$for my equation and it maybe be a little bit clearer to me. And how this algortihm wokrs? – Stefan4024 Mar 27 '13 at 11:03 • And if I use: $$a_n + b_n \sqrt{13} = (9 + 2 \sqrt{13})(\frac{3+\sqrt{13}}{2})^n$$ And for n = 3 I get:$a_3 = 292, b_3 = 81$and if I check those aren't solution – Stefan4024 Mar 27 '13 at 11:13 • @Stefan4024: Apologies for leading you astray, I thought you were dealing with equations of shape$x^2-13y^2=m$. Noticed it is$x^2-17y^2$. So we need to multiply any solutions by even powers of$4+\sqrt{17}$. – André Nicolas Mar 27 '13 at 11:33 • How did you get that number? Any explanation? – Stefan4024 Mar 27 '13 at 11:54 EDIT, January 2017: the property proved in this answer is in a book by Franz Lemmermeyer called Binary Quadratic Forms, Theorem 1.36, numbered page 37, pdf page 43 in my viewer. The part with$AC < 0, B > |A+C|$is formula (1.34) there. This is a proof of something I mentioned to awllower in comment, somewhere. In my diagrams of Conway's topograph, I draw the "river" as a straight line, and edges leaving it as perpendicular to the river. On page 20 in Conway's book, we read In other words, if you stray from the river, the values go up (in absolute value). So I started calling these orthogonal edges "straying edges." Now, most of the time, you get several straying edges in a row on the same side of the river. But then, you find a place where one straying edge is on one side of the river, the very next straying edge is on the other side. I decided to call this "crossing the river." Because I am clever that way. EDIT: Martin Weissman of U. C. Santa Cruz is writing a book on number theory that will include and expand upon the Conway topograph. He likes to call these special locations riverbends. His image, and the illustrations in Conway's book, have the river in something of a sinuous shape, for a while arcing around a positive value, then bending the other way and arcing around a negative value, and so on. As I drew my diagrams on graph paper and made all edges straight and the river a straight line, so this attractive image does not come across. The blog about progress on the book is HERE Let me emphasize that each edge with a little orange arrow and number refers to an indefinite quadratic form$\langle a,b,c \rangle.$The number$b$is the little orange number and is always positive or$0.$If you rotate the page, or screen, or your head, so that the arrow appears to point up, then the purple number in the open area on the left is$a,$while the purple number in the open area on the right is$c.$Since the numbers$a,c$are on different sides of the river, one is positive and one negative, so$ac < 0.$And we always have the same$\Delta = b^2 - 4 a c$is constant for all forms in the topograph, is positive but not a square. So in these cases,$b < \sqrt \Delta.$Now, it is very simple to describe those forms at which river crossing occurs. We must have$ac < 0,$$$a + c + b > 0$$ and $$a + c - b < 0.$$ Put these together, we get $$b > | a + c|.$$ Years ago, I noticed that the forms where river crossing occurs are Lagrange reduced. A discussion of this notion is at webpage and in Duncan A. Buell, Binary Quadratic Forms. Reduced means, with$\Delta = b^2 - 4 a c > 0,$: $$b > 0, \; ac < 0, \; b < \sqrt \Delta, \; \sqrt \Delta - b < 2 |a| < \sqrt \Delta + b, \; \sqrt \Delta - b < 2 |c| < \sqrt \Delta + b.$$ I should emphasize that the two final conditions, for$2 |a|$or for$2|c|,$are readily shown to be equivalent in the presence of the other conditions. This is Proposition 3.1 on pages 21-22 of Buell. Also items 1,2,3 after "Then the following are equivalent" on the webpage. THEOREM: if$\langle a,b,c \rangle$is reduced, then river crossing occurs at that form. PROOF: $$(|a| + |c|)^2 = a^2 + 2 |ac| + c^2 = a^2 - 2 a c + c^2 = (a-c)^2$$ $$\Delta - (|a| + |c|)^2 = b^2 - 4 a c - a^2 + 2 a c - c^2 = b^2 - a^2 - 2 a c - c^2 = b^2 - (a+c)^2.$$ So $$\sqrt \Delta \leq |a| + |c| \; \; \Longleftrightarrow \; \; b \leq |a+c|.$$ From the definition of reduced, square the inequality with$2 |a|$in the middle, $$\Delta - 2 b \sqrt \Delta + b^2 < 4 a^2 < \Delta + 2 b \sqrt \Delta + b^2.$$ Do the same with$2|c|$but then negate, $$-\Delta - 2 b \sqrt \Delta - b^2 < -4 c^2 < -\Delta + 2 b \sqrt \Delta - b^2.$$ Add and divide by 4, $$- b \sqrt \Delta < a^2- c^2 < b \sqrt \Delta,$$ or $$|a^2 - c^2| < b \sqrt \Delta.$$ Note $$||a| - |c|| = ||c| - |a|| = |a+c|$$ because$ac < 0.$So $$( |a| + |c|) |a+c| < b \sqrt \Delta.$$ If we assume that$b \leq |a+c|$then$\sqrt \Delta \leq |a| + |c|, $from which follows $$b \sqrt \Delta \leq |a^2 - c^2|,$$ which is a contradiction. So, actually,$b > |a+c|$and river crossing occurs at this form. $$\bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc$$ THEOREM: if river crossing occurs at$\langle a,b,c \rangle,$then the form is reduced. PROOF: We have$ac < 0$and$b > |a + c.|$This is a calculus type approach, so, like the first theorem, it applies to real numbers. Define $$\beta = |a+c|, \; \; \delta = \beta^2 - 4 a c.$$ So $$\delta = a^2 + 2 a c + c^2 - 4 a c = (a-c)^2,$$ and $$\sqrt \delta = |a| + |c|.$$ Case (I)$ |a| \geq |c|. $Then $$|a| - |c| = |a+c| = \beta.$$ Then $$\sqrt \delta + \beta = 2 |a|$$ and $$\sqrt \delta - \beta = 2 |c| \leq 2|a|.$$ Or $$\sqrt \delta - \beta \leq 2|a| = \sqrt \delta + \beta .$$ Case (II)$ |a| < |c|. $Then $$|c| - |a| = |a+c| = \beta.$$ Then $$\sqrt \delta + \beta = 2 |c|$$ and $$\sqrt \delta - \beta = 2 |a| < 2|c|.$$ Or $$\sqrt \delta - \beta < 2|c| = \sqrt \delta + \beta .$$ In either case, take real$t = b - \beta > 0$so that $$b = \beta + t > \beta.$$ Here is the calculus type part.$b$increases, strictly, with$t.$So$b^2$increases, strictly, with$t.$Then$\Delta = b^2 - 4 a c $increases, strictly, with$t.$And$\sqrt \Delta$strictly increases with$t.$Finally$\sqrt \Delta + b$strictly increases with$t.$Now, all along we are keeping$a,c$and$-4ac$constant. And from $$\Delta - b^2 = (\sqrt \Delta + b)(\sqrt \Delta - b) = - 4 a c$$ we find that $$(\sqrt \Delta - b) = \frac{-4ac}{\sqrt \Delta + b}$$ is strictly decreasing with$t.$As a result, with$t > 0,$in case (I) above, we find $$\sqrt \Delta - b < 2 |a| < \sqrt \Delta + b$$ so the form is reduced. in case (II) above, we find $$\sqrt \Delta - b < 2 |c| < \sqrt \Delta + b$$ so the form is reduced. $$\bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc$$ For convenience, here is Buell's Proposition 3.1. Suppose$b > 0,\; \; ac < 0,$and $$\sqrt \Delta - b < 2 |a| < \sqrt \Delta + b.$$ Then $$\Delta - b^2 = (\sqrt \Delta + b)(\sqrt \Delta - b) = - 4 a c = (2|a|) \cdot (2|c|).$$ Taking $$p =\sqrt \Delta - b, \; \; q =\sqrt \Delta + b, \; \; r = 2 |a|, \; \; s = 2|c|$$ we have four positive terms with $$p < r < q, \; \; \; pq = rs.$$ So also$ p < s < q.\$

• Nice expansion and explanation of a beautiful idea! – awllower Apr 26 '13 at 10:30