素数模高次同余方程的解法

与一次同余方程和同余方程组不同，高次同余方程没有统一的解法.解答高次同余方程目前还只能将完全剩余系带入逐一检验.然而人们可以对高次同余方程的解做些定性分析.本节主要讨论素数模同余方程的解的一些性质.设

其中p是素数，an≢0（modp）.

定理5.4.1　同余方程（5.4.1）与一个次数不超过p-1的素数模同余方程同解.

证明　用xp-x除f（x）得商式q（x）和余式r（x），即

f（x）=q（x）（xp-x）+r（x），r（x）=0或r（x）的次数小于p，

这里q（x）和r（x）是整系数多项式.据费马小定理，对任意整数x，有xp ≡x（modp）.于是

f（x）=q（x）（xp-x）+r（x）≡r（x）（modp）.

故方程（5.4.1）与r（x）≡0（modp）同解.证毕.

例5.4.2　找一个次数不超过6的同余方程与

x12+16x10-8x9-3x7+2x3-x≡0（mod7）

同解并求该方程的全部解.

解　由费马小定理知x7≡x（mod7）.于是

x12≡x6（mod7），x10≡x4（mod7），x9≡x3（mod7）.

注意到16≡2（mod7），8≡1（mod7），原方程与x6+2x4+x3-4x≡0（mod7）同解.将模7的完全剩余系-3，-2，-1，0，1，2，3带入检验得原方程的解为x≡0，1（mod7）.解毕.

下面的定理是法国大数学家拉格朗日（Lagrange，1736—1813）于1771年证明的.

定理5.4.3（拉格朗日）　设k≤n，x≡αi（modp），i=1，2，…，k是同余方程（5.4.1）的k个不同的解.则对任何整数x，有

f（x）≡（x-α1）…（x-αk）fk（x）（modp），

其中fk（x）是首项系数为an的n-k次多项式.

证明　对k进行归纳.当k=1时，用x-α1除f（x）得

f（x）=（x-α1）f1（x）+r，

其中r是常数.显然，f1（x）是首项系数为an的n-1次多项式.由x≡α1（modp）是同余方程（5.4.1）的解知r=f（α1）≡0（modp）.于是

f（x）=（x-α1）f1（x）+r≡（x-α1）f1（x）（modp）.

故结论对k=1的情况成立.

设结论对k-1个解的情况成立，即对任何整数x，有

其中fk-1（x）是首项系数为an的n-（k-1）次多项式.下面考虑k个解的情况.由（5.4.2）知

0≡f（αk）≡（αk-α1）…（αk-αk-1）fk-1（αk）（modp）.

由x≡αi（modp），i=1，2，…，k是同余方程（5.4.1）的k个不同的解知-αi，从而

（p，αk-αi）=1，i=1，2，…，k-1，

进而有（（αk-α1）…（αk-αk-1），p）=1，这导致fk-1（αk）≡0（modp）.用x-αk除fk-1（x）得fk-1（x）=（x-αk）fk（x）+s.于是s=fk-1（αk）≡0（modp）.这说明

fk-1（x）=（x-αk）fk（x）+s≡（x-αk）fk（x）（modp）.

将该式带入（5.4.2）得

f（x）≡（x-α1）…（x-αk-1）（x-αk）fk（x）（modp）.

由fk-1（x）是首项系数为an的n-（k-1）次多项式知fk（x）是首项系数为an的n-k次多项式.这表明结论对k个解的情况也成立.由归纳法原理知结论成立.证毕.

推论5.4.4　对任意正整数x和素数p，有

xp-1-1≡（x-1）（x-2）…（x-（p-1））（modp）.

证明　对任意α∈｛1，2，…，p-1｝，有（α，p）=1.由欧拉定理知αp-1≡1（modp）.这表明x≡1，2，…，p-1（modp）是xp-1≡1（modp）的p-1个不同的解.据定理5.4.3知(www.xing528.com)

xp-1-1≡（x-1）（x-2）…（x-（p-1））fp-1（x）（modp），

其中fp-1（x）是首项系数为1的0次多项式.这表明fp-1（x）=1.故结论成立.证毕.

作为定理5.4.3的推论，可以容易的证明著名的威尔逊定理.该定理是由英国数学家威尔逊（Wilson，1741—1793）于1770年左右发现，并由他的老师英国数学家华林（Waring，1736—1798）于同年宣布的.但这对师生没能给出这一定理的证明，给出证明的正是大数学家拉格朗日.

推论5.4.5　　　（威尔逊定理）若p为素数，则（p-1）！≡-1（modp）.

证明　当p=2时结论显然成立.当p＞2时，在推论5.4.4中令x=0即得结论.证毕.

推论5.4.6　同余方程（5.4.1）的解数不超过n.

证明　设x≡αi（modp），i=1，2，…，n+1是同余方程（5.4.1）的n+1个不同的解.则据定理5.4.3，对任何整数x，有

f（x）≡（x-α1）…（x-αn）fn（x）（modp），

其中fn（x）是首项系数为an的0次多项式.这表明fn（x）=an.故

f（x）≡an（x-α1）…（x-αn）（modp）.

用αn+1代替上式中的x，有

0≡f（αn+1）≡an（αn+1-α1）…（αn+1-αn）（modp）.

这表明p整除an（αn+1-α1）…（αn+1-αn）.注意到（an，p）=1，p整除

（αn+1-α1）…（αn+1-αn），

这导致p必整除某个αn+1-αi，其中i∈｛1，2，…，n｝.这与x≡αi（modp），i=1，2，…，n+1是同余方程（5.4.1）的n+1个不同的解矛盾.证毕.

注5.4.7　对合数模同余方程，上述推论不成立.例如，同余方程x3-3≡0（mod6）有6个解x≡0，1，2，3，4，5（mod6）.

定理5.4.8　设n是非负整数，p是素数且n≤p.则同余方程

f（x）=xn+an-1xn-1+…+a1x+a0≡0（modp）

有n个解当且仅当f（x）除xp-x的余式的所有系数均为p的倍数.

证明　用f（x）除xp-x得xp-x=q（x）f（x）+r（x），其中q（x），r（x）均为整系数多项式，q（x）的次数为p-n，r（x）=0或者r（x）的次数小于n.

设f（x）≡0（modp）有n个解.据费马小定理知，关于任意x∈Z，有xp-x≡0（modp）.故由等式xp-x=q（x）f（x）+r（x）知f（x）≡0（modp）的n个解均为r（x）≡0（modp）的解.据推论5.4.6，r（x）的系数必须均为p的倍数.

反之，设r（x）的系数均为p的倍数.由费马小定理知

x≡0，1，2，…，p-1（modp）

是xp-x≡0（modp）的p个解.由r（x）的系数均为p的倍数及等式

xp-x=q（x）f（x）+r（x）

知x≡0，1，2，…，p-1（modp）也是q（x）f（x）≡0（modp）的解，从而其解数为p.由p是素数知q（x）f（x）≡0（modp）的解数不大于q（x）≡0（modp）和f（x）≡0（modp）的解数之和.据推论5.4.6知q（x）≡0（modp）和f（x）≡0（modp）的解数不超过它们的次数p-n和n.于是q（x）≡0（modp）和f（x）≡0（modp）的解数只能是p-n和n.证毕.

需要指出的是，在定理5.4.8中，要求f（x）的首项系数为1.事实上，同余方程（5.4.1）同解于某个首项系数为1的素数模同余方程.请看下面的例子.

例5.4.9　判断2x3+3x+1≡0（mod7）是否有3个解.

解　由于（2，7）=1，故存在s，t∈Z使得2s+7t=1.事实上，容易看出2×（-3）+7×1=1.从等式2×（-3）+7×1=1看出（-3，7）=1.据命题4.1.4（3）知原同余方程与

（-3）（2x3+3x+1）≡0（mod7）

同解，也就是与

（1-7×1）x3+（（-3）×3）x+（（-3）×1）≡0（mod7）

同解，即与x3-2x-3≡0（mod7）同解.注意到

x7-x=（x3-2x-3）（x4+2x2+3x+4）+（12x2+16x+12），

据定理5.4.8知x2-2x-3≡0（mod7）的解数小于3，从而原方程的解数小于3.事实上，该方程有2个解x≡3，6（mod7）.解毕.