如何求解pell方程x^2-d*y^2=M

mathematica

x^2-d*y^2=M
其中M的绝对值大于d的平方根，
要是M的绝对值小于d的平方根，这个只要连分数就可以了！
但是大于怎么办？
比如
x^2-15y^2=61
我要的不是穷举法，我就是想知道如何求解


https://en.wikipedia.org/wiki/Pell%27s_equation

kastin

见https://bbs.emath.ac.cn/thread-15533-1-1.html
以及http://mathworld.wolfram.com/PellEquation.html最后部分（和相应的参考文献）

kastin

对于方程 `x^2-15y^2=61`，因为 `25^2\equiv 15 \pmod {61}`，故取二次无理分式展开 `\D\frac{25+\sqrt{15}}{61}=[0,2,8,\overline{1,6}]`，容易检验发现第三个完全商 `[8,\overline{1,6}]=5+\sqrt{15}`，其分母为1，故取第二个渐近分数 `p_2/q_2=[0,2]=1/2`，于是有 `(25q_2-61p_1)^2-15q_2^2=(-1)^261`.
因此得到最小解 `x_0=|25q_2-61p_1|=11,\;y=q_2=2`.
然后求标准形式 `x^2-15y^2=1` 的最小解，连分式展开 `\sqrt{15}=[3,\overline{1,6}]`，因为 `6=2\times 3`，故取渐近分数 `p_1/q_1=[3,1]=4`，得到最小解`x=p_1=4,\;y=q_1=1`，再根据上面链接中5楼的公式，可得通解。

mathematica

kastin 发表于 2019-3-19 20:48
对于方程 `x^2-15y^2=61`，因为 `25^2\equiv 15 \pmod {61}`，故取二次无理分式展开 `\D\frac{25+\sqrt{15} ...

我今天看华罗庚文集第274页,
感觉算看懂了,与你这个类似,
但是感觉他的办法似乎比你的好!