合数模高次同余方程简明实例

本节考虑合数模的同余方程.我们不准备系统的讨论合数模高次同余方程的理论，而是想通过具体的例子来诠释合数模高次同余方程的解法.详细的理论可参见参考文献［1］.通过这些例子可看出，合数模同余方程最终归结为素数模同余方程来求解.遗憾的是，素数模同余方程并没有非常有效的求解方法，目前还只能将其完全剩余系带入检验.先看一个素数幂模的高次同余方程.

例5.5.1　解同余方程x4+7x+4≡0（mod27）.

解　首先，注意以下事实：满足x4+7x+4≡0（mod27）之整数必满足

x4+7x+4≡0（mod9），

而满足x4+7x+4≡0（mod9）之整数必满足x4+7x+4≡0（mod3）.故先求

x4+7x+4≡0（mod3）

之解，再求x4+7x+4≡0（mod9）之解，最后求x4+7x+4≡0（mod27）之解.

（1）取模3的完全剩余系0，1，2，将其带入x4+7x+4≡0（mod3）中逐一检验可知它的解为x≡1（mod3）.即满足x4+7x+4≡0（mod3）的整数为3u+1型整数.

（2）在3u+1型整数中选出满足x4+7x+4≡0（mod9）之整数.设x=3u+1且x4+7x+4≡0（mod9）.则6u+3≡0（mod9），进而2u+1≡0（mod3）.将模3的完全剩余系0，1，2带入检验知u≡1（mod3）.这表明u是3v+1型整数.故满足x4+7x+4≡0（mod9）之整数为3u+1=3（3v+1）+1=9v+4型整数.

（3）在9v+4型整数中选出满足x4+7x+4≡0（mod27）之整数.设x=9v+4且x4+7x+4≡0（mod27）.则2v+2≡0（mod3）.解之得v≡2（mod3）.于是v为3s+2型整数.故满足x4+7x+4≡0（mod27）之整数为9v+4=9（3s+2）+4=27s+22型整数.这表明x4+7x+4≡0（mod27）的解为x≡22（mod27）.解毕.

由下面的例子可以看出，一般的合数模的同余方程最终可化归为素数幂模的同余方程组，然后借助孙子定理求解.(www.xing528.com)

例5.5.2　解同余方程31x4+57x3+96x+191≡0（mod225）.

解　　　（1）注意到225=32×52和（32，52）=1知31x4+57x3+96x+191≡0（mod225）与同余方程组

31x4+57x3+96x+191≡0（mod9），31x4+57x3+96x+191≡0（mod25）同解.

（2）先解31x4+57x3+96x+191≡0（mod9）.该方程就是4x4+3x3+6x+2≡0（mod9）.利用例5.5.1的方法可求得4x4+3x3+6x+2≡0（mod3）的解为x≡±1（mod3），进而求得4x4+3x3+6x+2≡0（mod9）的解为x≡4，5（mod9）.

（3）再解31x4+57x3+96x+191≡0（mod25）.该方程就是

6x4+7x3-4x-9≡0（mod25）.

利用例5.5.1的方法可求得6x4+7x3-4x-9≡0（mod5）的解为x≡1，2（mod5），进而求得6x4+7x3-4x-9≡0（mod25）的解为x≡1，22（mod25）.

（4）由上述讨论知，原方程的解为

x≡4（mod9），x≡1（mod25）或x≡5（mod9），x≡1mod25）或

x≡4（mod9），x≡22（mod25）或x≡5（mod9），x≡22（mod25）.由孙子定理可解得原方程的四个解x≡76，176，22，122（mod225）.解毕.