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$,

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

  • $\begingroup$ Where did you find this text? It is absolutely abominable. $\endgroup$ – Servaes Aug 25 '18 at 9:52
  • $\begingroup$ It's from a Chinese booklet on number theory, and is the only source that has this particular method mentioned. @Servaes $\endgroup$ – Trebor Aug 25 '18 at 10:03
  • $\begingroup$ math.stackexchange.com/questions/1719280/… $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ Anyone care to explain the downvote? $\endgroup$ – Servaes Aug 25 '18 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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