若正整数 a，b 互质，则有：（其中：$ phi(n)$ 为欧拉函数）
a
ϕ
(
n
)
≡
1
(
m
o
d
n
)
a^{\phi(n)}\equiv 1\qquad (mod\ n)
aϕ(n)≡1(mod n)
推论
费马小定理 若 p 是质数，则对于任意整数 a，有：
a
p
−
1
≡
1
(
m
o
d
p
)
a^{p-1}\equiv 1\qquad (mod\ p)
ap−1≡1(mod p)
证明（构造函数法）——（来自 李煜东 《算法竞赛进阶指南》）
若正整数 a，n 互质，则对任意正整数 a 有：
a
b
≡
a
p
m
o
d
ϕ
(
n
)
(
m
o
d
n
)
a^b \equiv a^{p\ mod \ \phi(n)}\qquad(mod\ n)
ab≡ap mod ϕ(n)(mod n)
证明（构造函数法）——（来自 李煜东 《算法竞赛进阶指南》）
快速幂
反复平方法 k 位二进制可以表示所有 [1,
2
k
−
1
2^k-1
2k−1] 的所有数（状态压缩），由此性质，对于给定一个取模数 p，预处理：
a
2
0
(
m
o
d
p
)
,
a
2
1
(
m
o
d
p
)
,
.
.
.
,
a
2
k
(
m
o
d
p
)
a^{2^0}\ (mod\ p),a^{2^1}(mod\ p),...,a^{2^k}(mod\ p)
a20 (mod p),a21(mod p),...,a2k(mod p) 然后将根据所求数的二进制表示每一位取出相乘即可求出要求的幂。
代码
int qickmi(int a,int k,int p)// a^k%p
{
int res = 1;
// 要转为 LL 防止溢出
while(k){if(k&1)
res = (long long)res * a % p;
a = (long long)a * a % p;
k >>= 1;
}
return res;
}
乘法逆元
定义 若 b，m 互质，并且有
b
∣
n
b\mid n
b∣n，则存在一个整数 x，使得
a
b
≡
a
∗
x
(
m
o
d
m
)
\frac{a}{b} \equiv a *x\qquad (mod\ m)
ba≡a∗x(mod m) 称 x 为 b mod m 的乘法逆元，记作：
b
−
1
(
m
o
d
m
)
b^{-1} \qquad (mod\ m)
b−1(mod m) 变形后也可以得到：
b
∗
b
−
1
≡
(
m
o
d
m
)
b*b^{-1} \equiv \qquad (mod\ m)
b∗b−1≡(mod m)
如果m是质数，则根据费马小定理：
b
m
−
1
≡
1
(
m
o
d
m
)
b^{m-1} \equiv 1 \qquad (mod\ m)
bm−1≡1(mod m) 代入上式
b
∗
b
m
−
1
≡
1
(
m
o
d
m
)
b*b^{m-1} \equiv 1 \qquad (mod\ m)
b∗bm−1≡1(mod m) 根据乘法逆元定义式，此时b的乘法逆元为：
b
p
−
2
b^{p-2}
bp−2