7. 数论四大定理（威尔逊定理、欧拉定理、费马小定理、孙子定理）

一、准备工作

点击查看数论基础知识

二、威尔逊定理

威尔逊定理给出了判定一个自然数是否为素数的充分必要条件。但是由于阶乘是呈爆炸增长的，其结论对于实际操作意义不大。

1. 定理及其变形

1. 当且仅当p为素数时，( p -1 )! ≡ -1 ( mod p )

2. 当且仅当p为素数时，( p -1 )! ≡ p-1 ( mod p )

3. 若p为质数，则p能被(p-1)!+1整除

4. 当且仅当p为素数时，p∣(p−1)!+1

2. 例题

hdu 2973 YAPTCHA

题解分析

三、欧拉定理（费马-欧拉定理）（Euler Theorem）

1. 定理

若n,a为正整数，且n,a互质，即gcd(a,n) = 1，则aφ(n)≡1(modn)a^{φ(n)} ≡ 1 (mod\space n)aφ(n)≡1(mod n)

2. 欧拉定理拓展

将欧拉定理拓展到A和C不互质的情况：

3. 举例

例1：（验证定理是否与结果相符）
令a = 3，n = 5，这两个数是互素的。
比5小的正整数中与5互素的数有1、2、3和4，所以φ(5)=4。
计算:aφ(n)a^{φ(n)}aφ(n) = 343^434 = 81，而 $81=80+1\equiv 1(mod5)$。
与定理结果相符。

例2：（实现简化幂的模运算）
计算72227^{222}7222的个位数。
解：
实际是求72227^{222}7222被10除的余数。
因为7和10互质，令a=7，n=10，则据欧拉函数公式易得：φ(10)=4。
由欧拉定理知：74≡1(mod10)7^4\equiv1(mod\space10)74≡1(mod 10)。
$\therefore$
7222(mod10)=[(74)55∗(72)](mod10)=[(74)55(mod10)]∗[(72)(mod10)]=155∗[72(mod10)]=49(mod10)=9(mod10)\begin{aligned} 7^{222}(mod\space10)&=[(7^4)^{55}*(7^2)](mod\space10)\\ &=[(7^4)^{55}(mod\space10)]*[(7^2)(mod\space10)]\\ &=1^{55}*[7^2(mod\space10)]\\ &=49(mod\space10)\\ &=9(mod\space10)\end{aligned}7222(mod 10)​=[(74)55∗(72)](mod 10)=[(74)55(mod 10)]∗[(72)(mod 10)]=155∗[72(mod 10)]=49(mod 10)=9(mod 10)​。
于是该72227^{222}7222的个位数就是9。

总结：
利用欧拉定理来简化幂模运算：ax≡ax%φ(m)(modm)a^x≡a^{x\%φ(m)}(mod\space m)ax≡ax%φ(m)(mod m)

4. 例题

hdu 1395 2^x(mod n) = 1

题解分析

四、费马小定理（Fermat’s little theorem）

1. 定理及其变形

对任意a和任意质数p，有ap≡a(modp)对任意a和任意质数p，有a^p\equiv a(mod\space p)对任意a和任意质数p，有ap≡a(mod p)

对任意a和任意质数p，当a与p互质时，有ap−1≡1(modp)对任意a和任意质数p，当a与p互质时，有a^{p-1}\equiv 1(mod\space p)对任意a和任意质数p，当a与p互质时，有ap−1≡1(mod p)

若p能被a整除，则ap−1≡0(modp)若p能被a整除，则a^{p-1} ≡0(mod\space p)若p能被a整除，则ap−1≡0(mod p)

2. 举例

计算 21002^{100}2100除以 13 的余数：

设a=2，p=13，正好满足gcd(a,p)=1。可以利用费马小定理：ap−1≡1(modp)a^{p-1}\equiv 1(mod\space p)ap−1≡1(mod p)。

∴213−1=1(mod13)⇒212=1(mod13)\therefore 2^{13-1}=1(mod\space 13)\Rightarrow2^{12}=1(mod\space 13)∴213−1=1(mod 13)⇒212=1(mod 13)

解：

2100(mod13)=212×8+4(mod13)=[(212)8⋅24](mod13)=[(212)8(mod13)]⋅[24(mod13)]=18⋅[16(mod13)]=3\begin{aligned} 2^{100}(mod\space 13)&=2^{12\times8+4}(mod\space 13)\\ &=[(2^{12})^8\cdot2^4](mod\space 13)\\ &=[(2^{12})^8(mod\space 13)]\cdot[2^4(mod\space 13)]\\ &=1^8\cdot[16(mod\space 13)]\\ &=3\end{aligned}2100(mod 13)​=212×8+4(mod 13)=[(212)8⋅24](mod 13)=[(212)8(mod 13)]⋅[24(mod 13)]=18⋅[16(mod 13)]=3​

3. 例题

hdu 4196 Remoteland

题解分析

五、孙子定理（中国剩余定理）

1. 定理及其变形

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

2. 基本公式的运用

中国剩余定理的孙子解法并没有什么高深的技巧，就是以下两个基本数学定理的灵活运用：

1. 如果 a%b=c , 则有 (a+kb)%b=c (k为非零整数)。
2. 如果 a%b=c，那么 (a*k)%b=kc (k为大于零的整数)。

3. 原理

关于中国剩余定理的原理讲解可以参考这篇博客，非常清楚！膜大神orz
中国剩余定理学习笔记

4. 逆元

求解中国剩余定理时，一般会用到逆元。
逆元实现的原理和代码总结可以参考这篇博客，非常全面！膜orz
逆元的求法总结（3种基本方法+4种实现）

5. 孙子定理模版

【接口】
int CRT(int a[],int m[],int n);
复杂度：O(nlogm)，其中m和每个mim_imi​同阶。
输入：a，m——第i个方程表示为x≡ai(modmi)x\equiv a_i(mod\space m_i)x≡ai​(mod mi​)
\space\space\space\space\space\space\space\space\space\space          n——方程个数
输出：方程组在[0,∏i=0n−1mi)[0,\prod_{i=0}^{n-1}m_i)[0,∏i=0n−1​mi​)中的解
调用外部函数：拓展欧几里得

【代码】

int CRT( int a[], int m[], int n )//中国剩余定理
{int M = 1;for(int i=0;i<n;++i) M *= m[i];int ret = 0;for(int i=0;i<n;++i){int x,y;int tm = M/m[i];extend_gcd(tm,m[i],x,y);//调用外部函数：拓展欧几里得ret = (ret+tm*x*a[i])%M;}return (ret+M)%M;
}

6. 顺便附上拓展欧几里得模版

【接口】
int extend_gcd(int a,int b,int &x,int &y);
复杂度：O(logN)，其中N和a，b同阶
输入：a，b——两个整数
\space\space\space\space\space\space\space\space\space\space          &x，&y——引用，ax+by=GCD(a,b)的一组解
输出：a和b的最大公约数
调用后x，y满足方程ax+by=GCD(a,b)

【代码】

int extend_gcd( int a, int b, int &x, int &y )//函数返回a,b的最大公约数
{if( b==0 ){x = 1;y = 0;return a;}else{int r = extend_gcd(b,a%b,y,x);y -= x*(a/b);return r;}
}