怎样求如下高次同余方程

wsc810

x^3+15x^2+29x+8=0(mod 45113)知道该方程有一根31,问其它两根怎么求？

wayne

从没玩过高次同余方程，期待ing……

我用数学软件算了一下，另外两个根是 19267，19496

litaoye

应该不止3个解吧？

wayne

3# litaoye

一般的方程其解不一定是三个的。
但这个却刚好只有三个，
貌似楼主是先知道了答案的。

medie2005

45113=197*229
因此，如果x0是x^3+15x^2+29x+8=0(mod 45113)的解，则必定同时满足：
x0^3+15x0^2+29x0+8=0(mod 197)
x0^3+15x0^2+29x0+8=0(mod 229)
分别分解模197和模229的多项式x^3+15x^2+29x+8，我们可以得到：
(11:14) gp > factormod(x^3+15*x^2+29*x+8,197)
%1 =
[Mod(1, 197)*x + Mod(7, 197) 1]

[Mod(1, 197)*x + Mod(39, 197) 1]

[Mod(1, 197)*x + Mod(166, 197) 1]

(11:14) gp > factormod(x^3+15*x^2+29*x+8,229)
%2 =
[Mod(1, 229)*x + Mod(198, 229) 1]

[Mod(1, 229)*x^2 + Mod(46, 229)*x + Mod(81, 229) 1]
然后，再解上面的模方程，再利用中国剩余定理得到原来的三次方程的解。

mathematica

我会使用穷举法来解决这个问题，毕竟那个模数不大，应该很快的

wsc810

#5,怎样求多项式方程在某个同余数下的分解

wsc810

为什么其它两根之差恰好是模45113的一个因子229,这其中是某种必然呢，还是纯属偶然现象？还有计算机是采用什么办法求解这种三次同余方程的，如果模数增大为大数，求解还容易吗？望不吝赐教。

qianyb

那你找找看是不是高次方程模M(M=a*b,a,b为素数)的解,其中两个解的差一定是a 或b

hujunhua

不是巧合。中国剩余定理保证的。
在最一般的情况下，模为pq(两个不同的素数之积)的一元3次同余方程有9个根。
对模p,  这9个根可分成3组，每组3根。每组内3根两两之差都是p的倍数。
对模q，亦成如此。不过组合不同。

本题只有3根，是因为还有6个虚根。