一、准备工作
点击查看数论基础知识
二、威尔逊定理
威尔逊定理给出了判定一个自然数是否为素数的充分必要条件。但是由于阶乘是呈爆炸增长的，其结论对于实际操作意义不大。
1. 定理及其变形
当且仅当p为素数时，( p -1 )! ≡ -1 ( mod p )
当且仅当p为素数时，( p -1 )! ≡ p-1 ( mod p )
若p为质数，则p能被(p-1)!+1整除
当且仅当p为素数时，p∣(p−1)!+1
2. 例题
hdu 2973 YAPTCHA
题解分析
三、欧拉定理（费马-欧拉定理）（Euler Theorem）
1. 定理
若n,a为正整数，且n,a互质，即gcd(a,n) = 1，则
a
φ
(
n
)
≡
1
(
m
o
d
n
)
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) =
3
4
3^4
34 = 81，而
81
=
80
+
1
≡
1
(
m
o
d
5
)
\space81=80+1\equiv1(mod\space5)
81=80+1≡1(mod 5)。 与定理结果相符。
例2：（实现简化幂的模运算） 计算
7
222
7^{222}
7222的个位数。 解： 实际是求
7
222
7^{222}
7222被10除的余数。 因为7和10互质，令a=7，n=10，则据欧拉函数公式易得：φ(10)=4。 由欧拉定理知：
7
4
≡
1
(
m
o
d
10
)
7^4\equiv1(mod\space10)
74≡1(mod 10)。
∴
\therefore
∴
7
222
(
m
o
d
10
)
=
[
(
7
4
)
55
∗
(
7
2
)
]
(
m
o
d
10
)
=
[
(
7
4
)
55
(
m
o
d
10
)
]
∗
[
(
7
2
)
(
m
o
d
10
)
]
=
1
55
∗
[
7
2
(
m
o
d
10
)
]
=
49
(
m
o
d
10
)
=
9
(
m
o
d
10
)
\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)。 于是该
7
222
7^{222}
7222的个位数就是9。
总结： 利用欧拉定理来简化幂模运算：
a
x
≡
a
x
%
φ
(
m
)
(
m
o
d
m
)
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
，
有
a
p
≡
a
(
m
o
d
p
)
对任意a和任意质数p，有a^p\equiv a(mod\space p)
对任意a和任意质数p，有ap≡a(mod p)
对
任
意
a
和
任
意
质
数
p
，
当
a
与
p
互
质
时
，
有
a
p
−
1
≡
1
(
m
o
d
p
)
对任意a和任意质数p，当a与p互质时，有a^{p-1}\equiv 1(mod\space p)
对任意a和任意质数p，当a与p互质时，有ap−1≡1(mod p)
若
p
能
被
a
整
除
，
则
a
p
−
1
≡
0
(
m
o
d
p
)
若p能被a整除，则a^{p-1} ≡0(mod\space p)
若p能被a整除，则ap−1≡0(mod p)
2. 举例
计算
2
100
2^{100}
2100除以 13 的余数：
设a=2，p=13，正好满足gcd(a,p)=1。可以利用费马小定理：
a
p
−
1
≡
1
(
m
o
d
p
)
a^{p-1}\equiv 1(mod\space p)
ap−1≡1(mod p)。
∴
2
13
−
1
=
1
(
m
o
d
13
)
⇒
2
12
=
1
(
m
o
d
13
)
\therefore 2^{13-1}=1(mod\space 13)\Rightarrow2^{12}=1(mod\space 13)
∴213−1=1(mod 13)⇒212=1(mod 13)
解：
2
100
(
m
o
d
13
)
=
2
12
×
8
+
4
(
m
o
d
13
)
=
[
(
2
12
)
8
⋅
2
4
]
(
m
o
d
13
)
=
[
(
2
12
)
8
(
m
o
d
13
)
]
⋅
[
2
4
(
m
o
d
13
)
]
=
1
8
⋅
[
16
(
m
o
d
13
)
]
=
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. 基本公式的运用
中国剩余定理的孙子解法并没有什么高深的技巧，就是以下两个基本数学定理的灵活运用：
如果 a%b=c , 则有 (a+kb)%b=c (k为非零整数)。如果 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
m_i
mi同阶。 输入：a，m——第i个方程表示为
x
≡
a
i
(
m
o
d
m
i
)
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
=
0
n
−
1
m
i
)
[0,\prod_{i=0}^{n-1}m_i)
[0,∏i=0n−1mi)中的解 调用外部函数：拓展欧几里得
【代码】
int CRT( int a[], int m[], int n )//中国剩余定理
{
int M = 1;
for(int i=0;i int ret = 0; for(int i=0;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; } }