Another quadratic Diophantine equation: How do I proceed?

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.

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.

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.
 
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.