数论四大定理 及在程序设计竞赛中的应用（稿）

（先挖个坑，有时间好好研究）

威尔逊定理

用法：

判别p是否为质数

p可整除 (p-1)!+1 是p为质数的充要条件

证明：

充分性

如果p不是素数，

当p=4时，显然（p-1)!≡6≡2(mod p),

当p>4时，若p不是完全平方数，则存在两个不等的因数a，b使得ab=p，

则(p-1)!≡nab≡0(mod p);

若p是完全平方数即p=k^2，因为p>4,所以k>2，k,2k<p，

(p-1)!≡n(k*2k)≡n'k^2≡0(mod p)。

必要性

若p是素数,取集合 A={1,2,3,...p -1}; 则A 构成模p乘法的缩系,即任意i∈A ,存在j∈A,使得:( i j ) ≡ 1 ( mod p )

那么A中的元素是不是恰好两两配对呢?

不一定,但只需考虑这种情况x^2 ≡ 1 ( mod p )

解得: x ≡ 1 ( mod p ) 或 x ≡ p - 1 ( mod p )

其余两两配对;故而( p - 1 )! ≡ 1﹡( p -1 ) ≡ -1 ( mod p )

欧拉定理（费马-欧拉定理）

用法：

用于求  a^φ(n)对n取模

若n,a为正整数，且n,a互素 最大公约数为1，（ 即gcd(a,n) = 1  )，则

a^φ(n) ≡ 1 (mod n)    =1

证明

设x（1），x（2），...，x(φ(n))是一个以n为模的简系，

则ax（1），ax（2），...，ax（φ(n) ）也是一个以n为模的简系（因为（a，n）=1）。

于是有ax（1）ax（2）...ax（φ(n) ）≡x（1）x（2）...x(φ(n))（mod n），

所以a^φ(n) ≡ 1 (mod n)。证毕。

孙子定理 ( 中国剩余定理 )

用法:

中国剩余定理说明：假设整数m1,m2, ... ,mn两两互质，则对任意的整数：a1,a2, ... ,an，方程组S有解，并可构造得出。

证明

将构造结果代入验证即可。

费马小定理

用法：

若p是质数，若p不能整除a，则 a^(p-1) ≡1（mod p），

                    若p能整除a，则a^(p-1) ≡0（mod p）。

若p是质数，且a,p互质，那么 a的(p-1)次方除以p的余数恒等于1。

证明

因为p是质数，且（a，p)=1，所以φ(p)=p-1。

由欧拉定理可得a^(p-1) ≡1（mod p）。证毕。

对于该式又有a^p ≡a（mod p），

所以，费马小定理的另一种表述为：假如p是质数，且(a,p)=1，那么a^p ≡a（mod p）。