So, I have understood how to solve Diophantine equations of the form
$$x^2-Dy^2=1.$$
However, when I was reading the solution of the generalized Pell's equation
$$x^2-Dy^2=c,$$
I got stuck. I knew how to solve it using continued fraction, but the book used an intriguing method, but skips over so much detail that I can't understand it. It seems to be using a method similar to Euclid's algorithm, which reduces the $c$ step by step, finally reaching $c=1$.
Here is the translated text:
Example 5. Find all integer solutions of the equation $x^2-15y^2=61$.
Solution: This is not a standard Pell's equation, therefore we need to transform it.
First, solve for the equation $l^2\equiv15(\mathrm{mod}\;61)\;(0\le l\le\frac{61}2)$, which is equivalent to $l^2=15+61h\;(l^2\le900)$. Since $0\le h\le \left[\frac{900}{61}\right]=14$, trying $h=0,1,\dots,14$ gives us $h=10, l=25$.
Next, find the solutions of $x^2_1-15y^2_2=10$, which reduces to to solving $l^2=15+10h\;(l\le\frac{10}{2}=5)$. We can see that $l=5,h=1$. Therefore $x_1=5, y_1=1$.
Next, solve the equation $x^2_2-15y^2_2=1$. This is a Pell's equation, whose fundamental solution is $x_2=4, y_2=1$.
Therefore, $x_2+\sqrt{15}y_2=\pm(4+\sqrt{15})^n$,
$x_1+\sqrt{15}y_1=\pm(4+\sqrt{15})^n(5\pm\sqrt{15})$,
$x+\sqrt{15}y=\pm(4+\sqrt{15})^n(5\pm\sqrt{15})(\frac{25\pm\sqrt{15}}{10})$.As the three $\pm$ signs are mutually independent, the solution to the equation is therefore
$$x+\sqrt{15}y=\pm(4+\sqrt{15})^n(14+3\sqrt{15})$$ and $$x+\sqrt{15}y=\pm(4+\sqrt{15})^n(11+2\sqrt{15})$$
Best Answer
The point is to first find a single solution to $x^2-15y^2=61$. Then every other solution is obtained by multiplying by units. I won't prove this here.
First, solving $l^2\equiv15\pmod{61}$ yields the identity $$25^2=15+61\cdot10\qquad\text{ so }\qquad \frac{(25+\sqrt{15})(25-\sqrt{15})}{10}=61.$$ Now suppose we have integers $z,w\in\Bbb{Z}$ such that $z^2-15w^2=10$. Then $x,y\in\Bbb{Z}$ defined by $$x+y\sqrt{15}:=(25\pm\sqrt{15})(z\pm w\sqrt{15}),$$ will satisfy $x^2-15y^2=61$. So we've reduced the problem to finding a solution to $z^2-15w^2=10$.
By the exact same method, solving $k^2\equiv15\pmod{10}$ yields the identity $$5^2=15+10\qquad\text{ so }\qquad(5+\sqrt{15})(5-\sqrt{15})=10.$$ Putting these together shows that $$61=\frac{(25+\sqrt{15})(25-\sqrt{15})}{(5+\sqrt{15})(5-\sqrt{15})} =\frac{1}{10^2}(5+\sqrt{15})(5-\sqrt{15})(25+\sqrt{15})(25-\sqrt{15}).$$ So all $x,y\in\Bbb{Z}$ with $x^2-15y^2=61$ are of the form $$x+y\sqrt{15}=u\cdot\frac{1}{10}(5\mp\sqrt{15})(25\pm\sqrt{15}),$$ where $u\in\Bbb{Z}[\sqrt{15}]^{\times}$ is any unit.
For values other than $61$ the process might be longer or shorter; here we were reduce to the classical Pell equation in two steps, consecutively solving the diophantine equations $$x^2-15y^2=61,\qquad x^2-15y^2=10,\qquad x^2-15y^2=1.$$ What can be said is that the right hand side decreases with every step, so this process does eventually terminate.