# Understanding a particular method of solving generalized version of Pell's equation

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})$$

• Where did you find this text? It is absolutely abominable. – Servaes Aug 25 '18 at 9:52
• It's from a Chinese booklet on number theory, and is the only source that has this particular method mentioned. @Servaes – Trebor Aug 25 '18 at 10:03
• math.stackexchange.com/questions/1719280/… – individ Aug 25 '18 at 10:16

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.