Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How would I find all the fundamental solutions of the Pell-like equation

$x^2-10y^2=9$

I've swapped out the original problem from this question for a couple reasons. I already know the solution to this problem, which comes from http://mathworld.wolfram.com/PellEquation.html. The site gives 3 fundamental solutions and how to obtain more, but does not explain how to find such fundamental solutions. Problems such as this have plagued me for a while now. I was hoping with a known solution, it would be possible for answers to go into more detail without spoiling anything.

In an attempt to be able to figure out such problems, I've tried websites, I've tried some of my and my brother's old textbooks as well as checking out 2 books from the library in an attempt to find an answer or to understand previous answers.

I've always considered myself to be good in math (until I found this site...). Still, judging from what I've seen, it might not be easy trying to explain it so I can understand it. I will be attaching a bounty to this question to at least encourage people to try. I do intend to use a computer to solve this problem and if I have solved problems such as $x^2-61y^2=1$, which will take forever unless you know to look at the convergents of $\sqrt{61}$.

Preferably, I would like to understand what I'm doing and why, but failing that will settle for being able to duplicate the methodology.

share|improve this question
    
Did you try what I suggested in November? Was it somehow unsatisfactory? –  Gerry Myerson May 13 '12 at 23:35
    
@GerryMyerson I do still have a link to the site. I'll try stepping through it with this problem again, but in the past when I've attempted it, the steps given in the step-by-step solution did not seem to match up with the method in the assossiacted website alpertron.com.ar/METHODS.HTM –  Mike May 13 '12 at 23:43

5 Answers 5

up vote 10 down vote accepted
+350

Let $u$ be an element of $\mathbb{Z}[\sqrt 5]$ of norm 1, i.e. $u = r + s \sqrt 5$ with $r^2-5s^2 = 1$.

The multiplication by $u$ in $\mathbb{Z}[\sqrt 5]$ turns any element $y$ of norm $44$ into another element $uy$ of norm $44$. View this multiplication operation on $\mathbb{Z}[\sqrt 5]$ as the transformation of the plane $f : (p,q) \rightarrow (pr+5qs,ps+qr)$, and look for its eigenvalues :

$f(\sqrt5,1) = (r\sqrt5+5s,r+\sqrt5s) = u(\sqrt5,1)$, and we have $f(- \sqrt5,1) = \frac 1u (- \sqrt5,1)$ as well.

If $u>1$ this means that $f$ is an operation that, when iterated, takes elements near the line $(p = - \sqrt5 q)$ and moves them over to the line $(p = \sqrt5 q)$ Now you want to find a sector of the plane so that you can reach the whole plane by taking its images by the iterates of $f$ and $f^{-1}$

Define $g(p,q) = \frac {p + \sqrt5 q}{p - \sqrt5 q}$, which is the ratio of the coordinates of $(p,q)$ in the eigenbasis of $f$. $g(f(p,q)) = \frac {pr+5qs + \sqrt5 (ps+qr)}{pr+5qs - \sqrt5 (ps+qr)} = \frac{(r+\sqrt5 s)(p + \sqrt5 q)}{(r-\sqrt5 s)(p - \sqrt5 q)} = (r+\sqrt5 s)^2 g(p,q)$.

Or alternately, define $g(y) = y/\overline{y}$, so that $g(uy) = uy/\overline{uy} = u^2 g(y)$.

Thus if you look at any point $(p,q)$, you know you can apply $f$ or $f^{-1}$ to turn it into $(p',q')$ such that $g(p',q') \in [1 ; u^2[$

Thus, a suitable sector of the plane is the set of points $(p,q)$ such that $g(p,q) \in [1 ; u^2[$ : if you find all the elements $y$ of norm $44$ such that $g(y) \in [1 ; u^2[$, then this means that the $u^ky$ will cover all the elements of norm $44$

Finally, the good thing is that $ \{y \in \mathbb{Z}[ \sqrt 5] / g(y) \in [1; u^2[, y\overline{y} \in [0; M] \}$ is a finite set, so a finite computation can give you all the elements of norm $44$ you need.


In the case of $p²-10q²=9$, a fundamental unit is $u = 19+6\sqrt{10}$, so replace $\sqrt 5,r,s$ with $ \sqrt {10},19,6$ in everything I wrote above.

In order to find all the solutions, you only need to check potential solutions in the sector of the plane between the lines $g(p,q) = 1$ and $g(p,q) = u^2$.

You can look at the intersection of the line $g(p,q)=1$ with the curve $p^2-10q^2 = 9$. $g(p,q)=1$ implies that $p+\sqrt{10}q = p- \sqrt{10}q$, so $q=0$, and then the second equations has two solutions $p=3$ and $p= -3$. It so happens that the intersection points have integer coordinates so they give solutions to the original equation.
Next, the intersection of the line $g(p,q) = u^2$ with the curve will be $u \times (3,0) = f(3,0) = (19*3+60*0, 6*3+19*0) = (57,18)$ and $u \times (-3,0) = (-57,-18)$.

So you only have to look for points on the curve $p^2-10q^2=9$ with integers coordinates in the section of the curve between $(3,0)$ and $(57,18)$ (and the one between $(-3,0)$ and $(-57,-18)$ but it is essentially the same thing).
You can write a naïve program :

for q = 0 to 17 do :
let square_of_p = 9+10*q*q.
if square_of_p is a square, then add (sqrt(square_of_p),q) to the list of solutions.

Which will give you the list $\{(3,0) ; (7,2) ; (13,4)\}$. These three solutions, together with their opposite, will generate, using the forward and backward interations of the function $f$, all the solution in $\mathbb{Z}^2$.

If you only want solution with positive coordinates, the forward iteration of $f$ on those three solutions are enough.
Also, as Gerry points out, the conjugate of $(7,2)$ generates $(13,4)$ because $f(7,-2) = (13,4)$. Had we picked a sector of the plane symmetric around the $x$-axis, we could have halved the search space thanks to that symmetry, and we would have obtained $\{(7,-2),(3,0),(7,2)\}$ instead.


One loop of this hypnotic animation represents one application of the function $f$. Each dot corresponds to one point of the plane with integer coordinates, and is moved to its image by $f$ in the course of the loop. The points are colored according to their norm (and as you can see, each of them stay on their hyperbolic branch of points sharing their norm), and I've made the yellow-ish points of norm 9 (the solutions of $x^2-10y^2 = 9$) a bit bigger. For example, the point at (3,0) is sent outside the graph, and the point at (-7,2) is sent on (13,4) (almost vanishing).

You can see that there are three points going through (3,0) during the course of one loop. They correspond to three representants of the three fundamental solutions of the equation. For each yellowish point on the curve $x^2-10y^2=9$, no matter how far along the asymptote it may be, there is an iterate of $f$ or $f^{-1}$ that sends it to one of those three fundamental solutions.

In order to find all fundamental solutions, it is enough to explore only a fundamental portion of the curve (a portion whose iterates by $f$ covers the curve), for example the fundamental portion of the curve between (-7,2) and its image by $f$, (13,4). To find the solutions on that portion, you set $y=-2,-1,0,1,2,3$ and look if there is an integer $x$ that makes a solution for each of those $y$.

Whichever fundamental portion of the curve you choose, you will find 3 solutions inside it, whose images by $f$ are sent to the next three solutions in the next portion of the curve, and so on.


Now there is a better procedure than the "brute search" I did to get all the solutions. It is an adaptation of the procedure to obtain a fundamental unit :

Start with the equation $x^2-10y^2 = 9$, and suppose we want all the positive solutions.
We observe that we must have $x > 3y$, or else $-y^2 \ge 9$, which is clearly impossible.
So, replace $x$ with $x_1 + 3y$.
We get the equation $x_1^2 + 6x_1 y - y^2 = 9$.
We observe that we must have $y > 6x_1$, or else $x_1^2 \le 9$.
In this case we quickly get the three small solutions $(x_1,y) = (1,2),(1,4),(3,0)$ which correspond to the solutions $(x,y) = (7,2),(13,4),(3,0)$.
Otherwise, continue and replace $y$ with $y_1 + 6x_1$.
We get the equation $x_1^2 - 6x_1y_1 - y_1^2 = 9$.
We observe that we must have $x_1 > 6y_1$, or else $-y_1^2 \ge 9$, which is clearly impossible.
So, replace $x_1$ with $x_2 + 6y_1$.
We get the equation $x_2^2 + 6x_2y_1 - y_1^2 = 9$.
But we already encountered that equation so we know how to solve it.

share|improve this answer
    
I think your explanation may be a bit over my head. I may need to refer back to this once I'm able to locate my old Linear Algebra text and see what makes sense. I assume $\overline x$ is $r-s\sqrt 5$? And what exactly is M? –  Mike Nov 15 '11 at 4:16
    
@Mike : precisely, conjugation turns $\sqrt5$ into $-\sqrt5$, and the norm of a number $y$ is the product of $y \overline{y}$. As for $M$, the point is that any region of the plane delimited by $A \leq y/ \overline{y} \leq B$ and $C \leq y \overline{y} \leq D$ is of finite area, so contains finitely many points with integer coordinates. So the line described by $\leq y \overline{y} = 44$ and $1 \leq y/ \overline{y} \lt x^2$ has finite length, and you can find all the points with integer coordinate on it in finite time. –  mercio Nov 15 '11 at 11:15
    
I've been meaning to reply on this answer for a while. I hadn't noticed until today that it had been heavily expanded. I tried to see if I could use the result (before all the changes) and thought that it just led to a messy system of inequalities. I tried delving deep into a book on Abstract Algebra. It makes a brief mention of $Z[\sqrt2]$ in an example and refers to Gaussian Integers as Z[i], but appears to have nothing in depth on this sort. Isn't a norm supposed to be always positive though? I think the part that's been tripping me up is the use of the eigenvalues. –  Mike May 17 '12 at 20:57
    
My aim now is the same as the aim before, I just figured an in-depth example would help and didn't want the old problem spoiled. As for brute force, one of the old answers attempted to solve the problem by more or less iterating all integers, then backtracking to determine which solutions were fundamental. You somehow seem to have narrowed the search space to exhaust all possibilities which is what I have been attempting to follow. For your pseudocode, why do you limit q to be from 0 to 17? In the meantime, I'll be delving more into a section on the uses of eigenvalues and eigenvectors. –  Mike May 17 '12 at 21:09
    
@Mike : Have you tried plotting the curves $x^2-10y^2 = k$, and plotting the action of the "multiplication-by-u-map" $f : (x,y) \mapsto (19x+60y,6x+19y)$ ? I'll try to add a diagram. Looking for the eigenvalues and eigenvectors of $f$ helps about understanding how $f$ acts on the plane, and when you understand what $f$ does, you immediately see how you can restrict the search for a set of fundamental solutions. –  mercio May 17 '12 at 21:46

It appears you are not satisfied with Gerry's website solver.

It is true that the continued fraction method gives all (primitive) solutions to $ x^2 - n y^2 = m,$ as long as $m < \sqrt n.$ This is a theorem of Lagrange.

So, when you take $9 = 3^2$ and find all solutions to $x^2 - 10 y^2 = 1$ by the continued fraction for $\sqrt {10},$ you do get all non-primitive solutions for $9$ by multiplying by $\pm 3.$

Now, $9 > \sqrt{10}.$ So the best you can do, which is fairly intricate but elementary, is Conway's topograph method, chapter 1 in CONWAY which can be bought at BUY_ME. The part you need to work with is pages 18-23, sections "Indefinite forms not representing $0$: The river" and "Integer-valued forms have periodic rivers." I really do not want to attempt to describe the method here. Please buy the book. If you do that, and email me, I can make a diagram giving enough detail of the "topograph" for $x^2 - 10 y^2,$ scan that somewhere as a pdf, and send you that. Conway does not actually give any fully worked out example. The fortunate thing for this problem is that the value $9$ occurs only along the river itself...see the Climbing Lemma, pages 11 and 20.

Meanwhile, once you have a column vector with entries $x,y$ that solves $x^2 - 10 y^2 = 9,$ another solution can be had by multiplying the column vector by the "automorph" $$ A \; = \; \left( \begin{array}{cc} 19 & 60 \\ 6 & 19 \end{array} \right) $$
or its inverse $$ A^{-1} \; = \; \left( \begin{array}{cc} 19 & -60 \\ -6 & 19 \end{array} \right). $$ For example $$ \left( \begin{array}{cc} 19 & 60 \\ 6 & 19 \end{array} \right) \left( \begin{array}{c} 7 \\ 2 \end{array} \right) = \left( \begin{array}{c} 253 \\ 80 \end{array} \right) $$ and, indeed, $253^2 - 10 \cdot 80^2 = 9.$ $$ \left( \begin{array}{cc} 19 & 60 \\ 6 & 19 \end{array} \right) \left( \begin{array}{c} 7 \\ -2 \end{array} \right) = \left( \begin{array}{c} 13 \\ 4 \end{array} \right) $$ and , indeed, $13^2 - 10 \cdot 4^2 = 9.$ Then $$ \left( \begin{array}{cc} 19 & 60 \\ 6 & 19 \end{array} \right) \left( \begin{array}{c} 13 \\ -4 \end{array} \right) = \left( \begin{array}{c} 7 \\ 2 \end{array} \right) $$ and $$ \left( \begin{array}{cc} 19 & 60 \\ 6 & 19 \end{array} \right) \left( \begin{array}{c} 13 \\ 4 \end{array} \right) = \left( \begin{array}{c} 487 \\ 154 \end{array} \right) $$ while $487^2 - 10 \cdot 154^2 = 9.$

See also RIVER.

Full cycle: Conway's method has some little tweaks compared to Lagrange/Gauss/Eisenstein. I think what I will do, since I do not know how to post the diagram [now added below], is just to put all the equivalent forms along the "river," always taking the first component positive (disagrees with Gauss) and always taking the equivalence matrix to have positive determinant. With these conventions, it is necessary to take some of the forms with negative middle coefficient. It's a lifestyle choice. I try not to judge.
 Will Drawing
So, when I say $\langle 1, 0, -10 \rangle $ is equivalent to $\langle 9, 2, -1 \rangle $ with matrix $A \in SL_2 \mathbf Z$ given by $$ A \; = \; \left( \begin{array}{cc} 7 & 3 \\ 2 & 1 \end{array} \right), $$ this means that $A$ is on the right and $$ \left( \begin{array}{cc} 7 & 2 \\ 3 & 1 \end{array} \right) \left( \begin{array}{cc} 1 & 0 \\ 0 & -10 \end{array} \right) \left( \begin{array}{cc} 7 & 3 \\ 2 & 1 \end{array} \right) = \left( \begin{array}{cc} 9 & 1 \\ 1 & -1 \end{array} \right). $$ When I say $\langle 1, 0, -10 \rangle $ is equivalent to $\langle 9, -2, -1 \rangle $ with matrix $A \in SL_2 \mathbf Z$ given by $$ A \; = \; \left( \begin{array}{cc} 13 & 3 \\ 4 & 1 \end{array} \right), $$ this means that $A$ is on the right and $$ \left( \begin{array}{cc} 13 & 4 \\ 3 & 1 \end{array} \right) \left( \begin{array}{cc} 1 & 0 \\ 0 & -10 \end{array} \right) \left( \begin{array}{cc} 13 & 3 \\ 4 & 1 \end{array} \right) = \left( \begin{array}{cc} 9 & -1 \\ -1 & -1 \end{array} \right). $$

With those in mind, a full cycle along Conway's river is $$\langle 1, 0, -10 \rangle, \left( \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right), $$

$$\langle 1, 2, -9 \rangle, \left( \begin{array}{cc} 1 & 1 \\ 0 & 1 \end{array} \right), $$

$$\langle 1, 4, -6 \rangle, \left( \begin{array}{cc} 1 & 2 \\ 0 & 1 \end{array} \right), $$

$$\langle 1, 6, -1 \rangle, \left( \begin{array}{cc} 1 & 3 \\ 0 & 1 \end{array} \right), $$

$$\langle 6, 4, -1 \rangle, \left( \begin{array}{cc} 4 & 3 \\ 1 & 1 \end{array} \right), $$

$$\langle 9, 2, -1 \rangle, \left( \begin{array}{cc} 7 & 3 \\ 2 & 1 \end{array} \right), $$

$$\langle 10, 0, -1 \rangle, \left( \begin{array}{cc} 10 & 3 \\ 3 & 1 \end{array} \right), $$

$$\langle 9, -2, -1 \rangle, \left( \begin{array}{cc} 13 & 3 \\ 4 & 1 \end{array} \right), $$

$$\langle 6, -4, -1 \rangle, \left( \begin{array}{cc} 16 & 3 \\ 5 & 1 \end{array} \right), $$

$$\langle 1, -6, -1 \rangle, \left( \begin{array}{cc} 19 & 3 \\ 6 & 1 \end{array} \right), $$

$$\langle 1, -4, -6 \rangle, \left( \begin{array}{cc} 19 & 22 \\ 6 & 7 \end{array} \right), $$

$$\langle 1, -2, -9 \rangle, \left( \begin{array}{cc} 19 & 41 \\ 6 & 13 \end{array} \right), $$

$$\langle 1, 0, -10 \rangle, \left( \begin{array}{cc} 19 & 60 \\ 6 & 19 \end{array} \right). $$

Various items, already mentioned. The first "automorph" is then $$ \left( \begin{array}{cc} 19 & 60 \\ 6 & 19 \end{array} \right). $$ The forms with negative middle coefficient are precisely those edges that point to the left. We switch from altering the first column to altering the second column, or back, precisely at the "reduced" forms, which in this case are only $\langle 1, 6, -1 \rangle$ and $\langle -1, 6, 1 \rangle,$ where we have written the latter as $\langle 1, -6, -1 \rangle$ to stick with beginning with a positive coefficient. Finally, there was no need to stray away from the river for this problem, $9$ is just small enough to spare us that extra complication.

share|improve this answer
    
Hmm... The review from Amazon does look promising, but I'm not sure I want to spend that kind of money on something I'm not even sure I can understand. It doesn't appear this is available at the library either, and I'm guessing this topic isn't covered in his book "The Book of Numbers". If it helps judge my level of knowledge, I majored in engineering in college. My brother was a math major and I often helped him with his assignments. My exposure to these equations was the Project Euler hazing ritual problem 66. :) –  Mike May 14 '12 at 0:36
    
@Mike, in that case, it depends on why this has become important to you. Is your brother still alive? Note that Problem 66 can be done entirely with continued fractions. You are asking about problems where that is not quite enough. Maybe you can get someone to copy pages 1-26 for you, send you paper copy or pdf. –  Will Jagy May 14 '12 at 2:32
    
Problem 66 is a problem that looks simple, until you try it. I'm guessing everyone tries a naive solution, then wonders why it takes hours to run. I think it's pretty much a rite of passage that people read the topic for that one and learn about Pell equations at which point they can look it up. But it seems a lot more complicated when dealing with some constant other than 1. As for my brother, I don't think he remembers much, although I do have all his old textbooks. I tried digging through his Abstract Algebra textbook to understand one of the previous answers. Helped some, not much. –  Mike May 14 '12 at 5:01
    
The other book is Binary Quadratic Forms by Duncan A. Buell, which is expensive but understandable. The bad news is that it does not cover Pell type equations with target numbers too large to be found by continued fractions. I describe the neighboring forms method in various MSE answers, it is a big improvement on continued fractions. –  Will Jagy May 14 '12 at 20:44
2  
I just added Will's hand-drawn diagram at his request. –  Joseph O'Rourke May 16 '12 at 20:22

You can type it into Dario Alpern's solver and tick the "step-by-step" button to see a detailed solution.

EDIT: I'm a little puzzled by Wolfram's three fundamental solutions, $(7,2)$, $(13,4)$, and $(57,18)$. It seems to me that there are two fundamental solutions, $(3,0)$ and $(7,2)$, and you can get everything else by combining those two with solutions $(19,6)$ of $x^2-10y^2=1$. Using mercio's formalism, $$(7-2\sqrt{10})(19+6\sqrt{10})=13+4\sqrt{10}$$ shows you how to get $(13,4)$; $$(3+0\sqrt{10})(19+6\sqrt{10})=57+18\sqrt{10}$$ shows you how to get $(57,18)$.

share|improve this answer

I'm going to give you the general method to obtain the fundamental solutions of the Diofantine equation $x^2-dy^2=f^2$.

First solution: We set $y=f-1$, $d=f^2+1$, $x=f^2-f+1$

Second solution: $y=f+1$, $d=f^2+1$, $x=f^2+f+1$

In your case $f^2=9$ and $d=f^2+1=10$. So the first solution is $7^2-10(2^2)=3^2$ and $13^2-10(4^2)=3^2$. From the two fundamental solutions we obtain infinite solutions of the equation $x^2-10y^2=3^2 $with the well known methods.

share|improve this answer
    
General method? How do you just say $d=f^2+1$? I mean in this one case it happens to be true, so you seem to be giving a fundamental solution for $x^2-(f^2+1)y^2=f^2$, which seems a tad too specific. I hadn't considered the last term being a square in this case. I had made the swap purely because it's solution was known. In the previous problem, which I didn't want spoiled, the constant on the right side of the equal was not square. Still, I'll give this a closer look later to see if I can figure out what you did and see if it could be applied for at least other values of d. –  Mike May 15 '12 at 17:14

Since I did not receive a complete answer from you for the solution I posted and because you are interested in a simple and quick method to find solutions to Diofantine equations $x^2-dy^2=f$ for many values of $d$, I will present another method that gives solutions for any $d$. In some cases the solutions are minimal.

Let's have the Diofantine equation $x^2-dy^2=f$. We set $x=m^2\pm m+k$ and $y=m\pm1$ where $k$ any non-zero natural number and $m$ any non-zero integer. From the division $x^2/y^2$ we obtain the values of $d$ and $f$, that solve the above equation.

Let’s have $x=m^2+m+k$ and $y=m+1$. From the division $x^2/y^2$ we obtain $d=m^2 + sk$ and $f=k^2–2km –2k$.

If $m=2, k=3$ we have $14^2-13\times4^2=-12$ which is reduced to $7^2-13\times2^2=-3$. Since $m$ can be any integer, for $k=2$ we obtain an infinite number of values of $d$.

Let’s have $x=m^2-m+k$ and $y=m-1$. From the division $x^2/y^2$ we obtain $d=m^2 +2k$ and $f=k^2+2km-2k$.

For $m=-5, k=3$ we obtain $33^2-31\times6^2=-27$ which is reduced to $11^2-31\times2^2=-3$. We can continue for any value of $m$.

Besides these general methods there are other specific for each value of $k$ which means we end up with an infinite number of formulas since $k$ takes all values from 1 to infinity. From these specific solutions we can obtain other fundamental solutions; in my opinion it is better to use only the general methods.

Lastly I will give you an example to find the solution of the Diofantine equation $x^2-61y^2=f$. The closest square to 61 is 49 and $61=49+2\times6$. From this we set $m=7, k=6$ and we obtain $62^2-61\times8^2=-60$ which reduces to $31^2-61\times4^2=-15$. If we apply the well known formulas we obtain another solution $1937^2-61\times248^2=15^2$. We can continue this process indefinitely, as you know. The general method which I present here is original mathematical work and is connected to hyperelliptic equations with global solutions.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.