威尔逊定理

初等数论四大定理

威尔逊定理、欧拉定理、剩余定理（孙子定理）、费马小定理

威尔逊定理：

当且仅当p为素数时，有：(p-1)!≡-1(modp)

欧拉定理：

若n,a为正整数，且n,a互质，(a,n)=1，则：a^φ(n)≡1(modn)

剩余定理（孙子定理）：

若有一些两两互质的整数m

1

,m

2

,…,m

n

，则对任意的整数a

1

,a

2

,…,a

n

，以下联立同余方程组对模

m

1

,m

2

,…,m

n

有公解：x≡a

1

(modm

1

),x≡a

2

(modm

2

),……,x≡a

n

(modm

n

)

费马小定理：

若p是质数，且(a,p)=1，则：a^(p-1)≡1(modp)

之前一直认为费马小定理的证明很复杂，但是懂了欧拉定理之后就迎刃而解了.

首先，我们需要知道欧拉定理是什么：数论上的欧拉定理，指的是ax≡1(modn)

这个式子实在a和n互质的前提下成立的.为什么成立呢？下面来证一下.

首先，我们知道在1到n的数中，与n互质的一共有φ(n)φ(n)个，所以我们把这φ(n)φ(n)个数

拿出来，放到设出的集合X中，即为x1,x2……xφ(n)x1,x2……xφ(n).

那么接下来，我们可以再设出一个集合为M，设M中的数为：

m1=a∗x1m2=a∗x2……mφ(n)=a∗xφ(n)m1=a∗x1m2=a∗x2……mφ(n)=a∗xφ(n)

下面我们证明两个推理：一、M中任意两个数都不模n同余.

反证法.证明：假设M中存在两个数设为ma,mbma,mb模n同余.

即ma≡mbma≡mb移项得到：ma−mb=n∗kma−mb=n∗k

再将m用x来表示得到:a∗xa−a∗xb=n∗ka∗xa−a∗xb=n∗k

提取公因式得到a∗(xa−xb)=n∗ka∗(xa−xb)=n∗k

我们现在已知a与n互质，那么式子就可以转化为：xa−xb≡0（modn)xa−xb≡0（modn)，因

为a中没有与n的公因子（1除外）所以a对模n同余0并没有什么贡献.

又因为xa,xbxa,xb都是小于n的并且不会相同，所以xa−xbxa−xb一定是小于n的，那么上述

的式子自然全都不成立.

假设不成立.

证得：M中任意两个数都不模n同余.

二、M中的数除以n的余数全部与n互质.

证明：我们已知mi=a∗ximi=a∗xi.

又因为a与n互质，xixi与n互质，所以可得mimi与n互质.

带入到欧几里得算法中推一步就好了.

即gcd(a∗xi,n)=gcd(mi,n)=gcd(n,mimodn)=1

证毕.

根据我们证得的两个性质，就可以开始推式子了.

首先，根据第二个性质可以知道，M中的数分别对应X中的每个数模n同余.

所以可以得到：

m1∗m2∗……∗mφ(n)≡x1∗x2∗……∗xφ(n)(modn)m1∗m2∗……∗mφ(n)≡x1∗x2∗……∗xφ(n)(mo

dn)

现在我们把mimi替换成x的形式，就可以得到：

a∗x1∗a∗x2∗……∗a∗xφ(n)≡x1∗x2∗……∗xφ(n)(modn)a∗x1∗a∗x2∗……∗a∗xφ(n)≡x1∗x2∗……

∗xφ(n)(modn)

很显然，我们应该移项了，但是在移项之前，我们认为这么多的a很烦，那么就先乘起来：

aφ(n)∗(x1∗x2……∗xφ(n))≡x1∗x2……∗xφ(n)(modn)aφ(n)∗(x1∗x2……∗xφ(n))≡x1∗x2……∗

xφ(n)(modn)

很开心，我们终于凑出了aφ(n)aφ(n),那么就开始移项吧：

(aφ(n)−1)∗(x1∗x2……∗xφ(n))≡0(modn)(aφ(n)−1)∗(x1∗x2……∗xφ(n))≡0(modn)

然后，就出来啦：aφ(n)≡1(modn)aφ(n)≡1(modn)

证毕.

用现代数学的语言来说明的话，中国剩余定理给出了以下的一元线性同余方程组：

有解的判定条件，并用构造法给出了在有解情况下解的具体形式.

中国剩余定理说明：假设整数m1,m2,...,mn两两互质，则对任意的整数：a1,a2,...,an，方程组

有解，并且通解可以用如下方式构造得到：

设

是整数m1,m2,...,mn的乘积，并设

是除了mi以外的n-1个整数的乘积.

设为模的数论倒数(为模意义下的逆元)

方程组的通解形式为

在模的意义下，方程组只有一个解：

证明：从假设可知，对任何，由于

，所以这说明存在整数使得

这样的叫做模的数论倒数.考察乘积可知：

所以

满足：

这说明就是方程组的一个解.另外，假设和都是方程组的解，那么：

而

两两互质，这说明整除.所以方程组的任何两个解之间必然相差

的整数倍.而另一方面，

是一个解，同时所有形式为：

的整数也是方程组的解.所以方程组所有的解的集合就是：