我们遇到过一元一次同余式，也处理过特殊形状的一元二次同余式：x^2=D mod p,其中 p是一个素数。对于一般的情况：f(x)=anx^n+an-1x^n-1+...+a1x+a0=0 mod m (a0,a1,...an是整数,m是任意自然数），我们来看什么是此同余式的根。首先假设模 m等于两两互素的整数 a,b,c,...之积，我们来看要解同余式
f(x)=0 mod m (1)
只要会解下面的每一个同余式：
f(x)=0 mod a
f(x)=0 mod b (2)
f(x)=0 mod c
......
我们可以看出（1）的每一个解是同余式组（2）的各式的解；因为如果对于 x的某个整数值，f(x)可被 p整除，当然就能被 a,b,c,...之一整除；反过来表明，如果知道了整数 u,v,w,...分别满足（2）的各式，就能保证求出（1）的一解。而这些是以如下的中国剩余定理（孙子定理）为基础的。
给出两两互素的整数 a,b,c,...以及整数 u,v,w,...求一个数使其满足
x=u mod a,x=v mod b,x=w mod c ,...
像上面那样以 m表乘积 abc...,首先求一些整数 A,B,C,...,使其依次被整数 m/a,m/b,m/c,...整除而依次关于模 a,b,c,...余1，为此，只须将下列同余式
mA'/a=1 mod a
mB'/b=1 mod b
mC'/c=1 mod c
......
对 A',B',C',...解出，这是完全办得到的，因为m/a=bc...与 a互素，m/b与 b互素，...等等；然后取
A=mA'/a,B=mB'/b,C=mC'/c,...
令 x0=Au+Bv+Cw+...,则整数x0适合所求条件。事实上，B、C、...被 a整除，故有
x0=Au=u mod a
等等，适合条件的其他 x值是在x0上加 m的一个倍数，因为差数 x-x0应被 a,b,c,...整除，因此也应被 m整除。此法有这样一个优点，A,B,C,...各数的计算与 u,v,w,...无关，而仅由 a,b,c,...确定。这就是中国剩余定理。
我们看到方程（1）与方程组（2）同解。因此同余式（1）的求解，可以将 m分解成素因数，将它化成求解一些形如
f(x)=0 mod p^n （3）
的同余式，式中 p是素数。
需要注意的是，凡是同余式（3）的解，也一定是同余式 f(x)=0 mod p^(n-1) 的解。假设我们会解后一个同余式，则（3）式的每一个解应该与后一个同余式的某一个解关于模 p^(n-1)同余;因此，若以x0表后一个同余式的一个解，我们应该设
x=x0+yp^(n-1)
y是一个整数由同余式
f(x0+yp^(n-1))=0 mod p^n
来确定，这个同余式等价于一个一次同余式，因此，如果会解模 p的同余式，就会解模 p^2的同余式，再去解模 p^3的同余式等等。
此法也适合于求解二次同余式：x^2-D=0 mod p^n,这个同余式有解的条件是同余式：x^2-D=0 mod p有解。还可以看出前一个同余式只能有两个不同余模 p^n的解。同余式
x^2-D=0 mod 2^n
中，D是奇数，当 n是 1或者 2时以一切奇数为解；所以在第一种情况下它有一个解，在第二种情况下有两个解。同余式
x^2-D=0 mod 8
中，D为奇数，只当 D=1 mod 8时才有解，这时有四个不同的解，即1，3，5，7。同余式
x^2-D=0 mod 2^n
中，D为奇数，n>3,此式只当 D=1 mod 8时有解。若此条件满足，则同余式有四个不同的解。在有了上面这些结果之后，就不难研究同余式
x^2-D=0 mod m
是否有解（式中 D为奇数，且与 m互素，m的形状是 p^aq^br^c...或者 2^np^aq^br^c...，p,q,r,...是奇素数),并计算互异解答的个数。
下面研究模是素数的情形下，同余式 f(x)=0 mod p的解的问题，因为前面的讨论都归结为素数模的情况了。
设以整数 a代替多项式 f(x)中的 x，得出0 mod p，即是说f(a)被 p整除，则 f(x)一定也被x-a模 p整除,事实上由多项式理论，f(x)-f(a)能被x-a整除，商是一个整系数多项式 g(x);所以有恒等式：
f(x)=f(a)+(x-a)g(x)
但是由假设，f(a)能被 p整除,所以得证。
反之，若f(x)被x-a模 p整除，则明显地 f(a)也被 p整除。
如果有若干个整数 a,b,c,...两两关于模 p互素，使得多项式f(x)被x-a,x-b,x-c,...整除，则f(x)一定也被(x-a)(x-b)(x-c)...模 p整除。证明与前类似。
一个 n次多项式不可能有多于 n个的两两模 p互素的值来代替 x使 f(x)=0 mod p的。事实上，设f(x)=0 mod p有 n个两两模 p互素的根 a,b,c,...l，并且x^n的系数是 K,则有恒等式：
f(x)=K(x-a)(x-b)(x-c)...(x-l)+pg(x)
其中 g(x)是整系数多项式，并设x0是跟 a,b,c,...,l都模 p不同余的整数，并且f(x0)=0 mod p,那就应该有：
K(x0-a)(x0-b)(x0-c)...(x0-l)=0 mod p
但是这是不可能的。
我们用以上的理论来看一个例子，按照费尔马小定理，同余式
x^(p-1)-1=0 mod p
应该有p-1个不同的根,即1,2,3,...p-1;并且当 p > 2 时有恒等式：
x^(p-1)-1=(x^(p-1)/2-1)(x^(p-1)/2+1)
所以同余式 x^(p-1)/2-1=0 mod p 和 x^(p-1)/2+1=0 mod p 各有（p-1)/2个根；这些我们前面已经知道了；前一个同余式的根是 p的二次剩余，后一个同余式的根是 p的二次非剩余。
从上面的结论还可以用来证明威尔逊定理。p-1次同余式 x^(p-1)-1=0 mod p 有p-1个互异的根:1,2,...,p-1;所以 x^(p-1)-1能被乘积(x-1)(x-2)...(x-p+1)模 p整除，并且最高次项系数是1，所以有恒等式：
x^(p-1)-1=(x-1)(x-2)...(x-p+1)+pg(x)
其中g(x)是整系数多项式；由此可知多项式：
x^(p-1)-1-(x-1)(x-2)...(x-p+1)
的各个系数都能够被 p整除，就是说，这个多项式模 p等于0，特别是常数项也应该如此，即：
1*2*3*...(p-1)+1=0 mod p
这让我们看到了费尔马小定理与威尔逊定理之间的关系，乘积：
(x-1)(x-2)...(x-p+1)
的展开式中，除了首末两项外所有各项的系数都能被 p整除，但是首末两项正是联系费尔马小定理与威尔逊定理的关键所在。 |
![[漫猫]动漫论坛](comicat/images/logo.jpg){kind=logo}
IP卡
狗仔卡
提升卡
置顶卡
沉默卡
变色卡
显身卡