数学研发论坛

 找回密码
 欢迎注册
查看: 287|回复: 4

[求助] 不定方程$x^2-a*y^2=p$求解

[复制链接]
发表于 2018-9-12 22:09:32 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
$x^2+ay^2=p$,$p$是素数,该类型不定方程的求解可使用如下算法

先求$t^2=-a (mod p)$,其中$t<p/2$


然后计算连分数$t/p=[a_0,a_1,a_2,...,a_s]$

要求$q_n<\sqrt{p}                     q_{n+1}>\sqrt{p}$

$(t*q_n-p*p_n)+a*q_n^2=p$

即为解

举例  $x^2+29y^2=1997$

$574^2=-29 (mod  1997)$

$\sqrt{1997}=44.6878$

$574/1997=[0, 3, 2, 11, 2, 5, 2]$

$p_n/q_n=[0,3,2]=2/7$                        $p_{n+1}/q_{n+1}=23/80$

$(574*7 - 1997*2=24)^2+29*7^2=1997$



在计算$x^2-a*y^2=p$的时候,如法炮制,却多出一个负因子,错在哪里,求正确解法

  $x^2-29y^2=1997$

$842^2=29(mod 1997)$

$842/1997=[0, 2, 2, 1, 2, 4, 2, 2, 4]$


$8/19=[0, 2, 2, 1, 2]$                    $35/83=[0, 2, 2, 1, 2, 4]$

$(842*19-1997*8=22)^2-29*19^2=-1997*5$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-9-28 15:18:15 | 显示全部楼层
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-9-30 13:48:11 | 显示全部楼层
本帖最后由 kastin 于 2018-9-30 13:50 编辑

设 `t^2\equiv a\pmod{p}`,所以 `p\mid a-t^2`,从而二次无理根式 `(t+\sqrt{a})/p=[a_0,a_1,\cdots]` 对应的完全商与本身具有相同形式。
设其第`m` 个渐近分数为`p_m/q_m`,第 `m+1` 个完全商为 `(c+\sqrt{a})/h`,那么\[\begin{align*}(tq_m-pp_m)^2-aq_m^2=(-1)^mph\tag{1}\end{align*}\]因此只需要找到找到合适的`t`使得展开到某个完全商的分母 `h` 满足上式,那么不定方程 `x^2-ay^2=\pm ph` 的一个正整数解就是 `x=|tq_m-pp_m|,\;y=|q_m|`

比如 `x^2-29y^2=1997` 若令 `p=1997` 作为分母,那么 `h=1`,而 `1155^2\equiv 29\pmod{1997}`,故 `t=1155`.
因为 `\D\frac{1155+\sqrt{29}}{1997}=[0,1,1,2,1,1,2,\overline{2,10,2,1,1}]`(上划线表示循环节),计算可知第9个完全商`[10, 2, 1, 1, \overline{2, 10, 2, 1, 1}]=5+\sqrt{29}` 的分母为 `1`,故第8个渐金分数为 `[0,1,1,2,1,1,2,2]=43/74`,从而有\[(1155\times74 - 1997\times43)^2 - 29\times74^2=(-1)^8\cdot1997=1997\]于是解为 `x=1997\times43-1155\times74=401,y=74`.

当然,也可取 `t=842`,此时展开为 `\D\frac{842+\sqrt{29}}{1997}=[0,2,2,1,4,\overline{10,2,1,1,2}]`,而第6个完全商 `\overline{10,2,1,1,2}=5+\sqrt{29}` 的分母为 `1`,所以第5个渐近分数为 `14/33`,故`(842\times33 - 1997\times14)^2 - 29\times33^2=(-1)^5\cdot1997=-1997`. 相差一个负号,故可考虑使用无理式的共轭进行展开 `\D\frac{842-\sqrt{29}}{1997}=\frac{-842+\sqrt{29}}{-1997}=[0,2,2,1,1,2,\overline{2,10,2,1,1}]`,过程仍然不变,第8个完全商分母为1,而第7个渐近分数为 `31/74`故\[(-842\times74 -(-1997)\times 31)^2 - 29\times 74^2=(-1)^7\cdot(-1997)=1997\]于是解为 `x=|-842\times74 -(-1997)\times 31|=401,y=74`.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-9-30 14:42:02 | 显示全部楼层
方程
\[x^2-29y^2=1997\]
的解答:

迭代初始值
x = 401
y = 74
或者
x = -401
y = -74
或者
x = -401
y = 74
或者
x = 401
y = -74

迭代公式
xn+1 = 9801 ⁢xn + 52780 ⁢yn
yn+1 = 1820 ⁢xn + 9801 ⁢yn

或者
xn+1 = 9801 ⁢xn - 52780 ⁢yn
yn+1 = - 1820 ⁢xn + 9801 ⁢yn
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-9-30 14:54:22 | 显示全部楼层
特别地,若在 `(1)` 中令$t=0,p=1$,便有\[p_m^2-aq_m^2=(-1)^mh\tag{2}\]因此`p_m,q_m` 就是不定方程 `x^2-ay^2=\pm h` 的一组解。这里 `h` 必须满足 `|h|\leqslant 2\lfloor\sqrt{a}\rfloor`.

另外还有如下定理:
若`(x_1,y_1)` 和 `(x_2,y_2)` 分别为方程 `x^2-ay^2=r_1` 和 `x^2-ay^2=r_2` 的一组解,那么 `(x_1x_2\pm ay_1y_2,x_1y_2\pm x_2y_1)` 为方程 `x^2-ay^2=r_1r_2` 的解。

于是可通过分解因式的方式将方程右端拆成两个简单因子之积,然后直接展开 `\sqrt{a}`,找出对应的渐近分数,然后利用上述定理可得原方程的解。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2018-11-18 09:15 , Processed in 0.048550 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表