同余理论学习笔记
1.对于正整数m,a,b满足m整除a-b存在k使得a=b+km，则称a,b在模m意义下同余，记做a ≡ b
(mod m)
2.任意两个在模m下同余的数相加依然同余
3.若两个数在某一模数下同余，那么在这两个数的约数下也同余
4.如果对于 a ≡ b (mod m)，若 d|a, d|b, d|m，则 a/d ≡b/d(mod m/d)
5.对于 a ≡ b (mod m)，有 gcd(a, m) = gcd(b, m) 6.对于任意整数 a，存在整数 q, r 使得 a = mq + r, 0 ≤ r < m，
所有可能的 r 构成一个模 m 的剩余系，其定义了整数在模意
义下的等价类 {a mod m|a ∈ Z}
ps：前面可以是一个函数，只有剩余系有n-1个数是称为完全剩余系，所以说剩余系有可能不完全
7.对于质数 m，若 gcd(a, m) = 1，b 是任意整数，则
{(ax + b) mod m|x ∈ Z} = {x mod m|x ∈ Z}
8.对于质数 m1 和 m2，若 gcd(m1, m2) = 1，则
{(m2x1 + m1x2) mod m1m2|x1 ∈ Z, x2 ∈ Z} =
{x mod m1m2|x ∈ Z}
9.对于正整数 m，{a mod m|a ∈ Z, gcd(a, m) = 1} 构成一个模
m 的简化剩余系，该集合的大小被定义为欧拉函数 ϕ(m)
ps：与一个整数互质的数的数量称为这个数的欧拉函数
10.对于正整数 m，若 gcd(a, m) = 1，则 {ax mod m|x ∈
Z, gcd(x, m) = 1} = {x mod m|x ∈ Z, gcd(x, m) = 1}
11对于正整数 m1 和 m2，若 gcd(m1, m2) = 1，则
{(m2x1 + m1x2) mod m1m2|x1 ∈ Z, gcd(x1, m1) = 1, x2 ∈
Z, gcd(x2, m2) = 1} = {x mod m1m2|x ∈ Z, gcd(x, m1m2) =
1} 12.对于正整数 m，若 gcd(a, m) = 1，则存在 s 满足 1 ≤ s < m,
sa ≡ 1 (mod m)，也即存在整数 s, t 满足 sa + tm = 1，记 s
为 a 在模 m 意义下的乘法逆元 a
−1
13.扩展欧几里得算法：寻找二元一次不定方程
sx + ty = gcd(x, y) 的一组整数解 (s, t)
void exgcd(int a,int b,int &x,int &y)
{
if(!b) { x=1; y=0; }
else { exgcd(b,a%b,y,x); y-=x*(a/b); }
}
14.
中国剩余定理：对于两两互质的 mi，同余方程组
x ≡ r1 (mod m1)
x ≡ r2 (mod m2)
· · ·
x ≡ rk (mod mk),
的解为∑riMiMi(mod M) 其中 M =mi的乘积Mi=M/mi Mi为Mi的逆元(mod mi)
15.费马小定理：若 p 是质数，则对于任意整数 a 有 a^p ≡ a(mod p)
16.欧拉定理：若 m 是正整数，gcd(a, m) = 1，则有 a
ϕ(m) ≡ 1（mod m)
17.威尔逊定理：若 p 是质数，则有 (p − 1)! ≡ −1 (mod p)