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 (modspace n)$

2. 欧拉定理拓展

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

3. 举例

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

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

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

4. 例题

hdu 1395 2^x(mod n) = 1

题解分析

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

1. 定理及其变形

$对任意a和任意质数p，有a^pequiv a(modspace p)$

$对任意a和任意质数p，当a与p互质时，有a^{p-1}equiv 1(modspace p)$

$若p能被a整除，则a^{p-1} ≡0(modspace p)$

2. 举例

计算 $2^{100}$除以 13 的余数：

设a=2，p=13，正好满足gcd(a,p)=1。可以利用费马小定理：$a^{p-1}equiv 1(modspace p)$。

$herefore 2^{13-1}=1(modspace 13)Rightarrow2^{12}=1(modspace 13)$

解：

$egin{aligned} 2^{100}(modspace 13)&=2^{12 imes8+4}(modspace 13)\ &=[(2^{12})^8cdot2^4](modspace 13)\ &=[(2^{12})^8(modspace 13)]cdot[2^4(modspace 13)]\ &=1^8cdot[16(modspace 13)]\ &=3end{aligned}$

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和每个$m_i$同阶。
输入：a，m——第i个方程表示为$xequiv a_i(modspace m_i)$
$spacespacespacespacespacespacespacespacespacespace$n——方程个数
输出：方程组在$[0,prod_{i=0}^{n-1}m_i)$中的解
调用外部函数：拓展欧几里得

【代码】

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——两个整数
$spacespacespacespacespacespacespacespacespacespace$&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;
	}
}