* 费马小定理
若 p 是质数,则对于任意整数 a ,有。
* 欧拉定理
若正整数 a,n 互质,则。
* 欧拉定理推论
若正整数 a,n 互质,则对于任意正整数 b,有。
特别的,当 a,n 不一定互质且 b > Φ(n) 时,有。
* Dirichlet卷积
* 莫比乌斯函数
* 莫比乌斯反演
对于两个数论函数 f(n),g(n),
若
则有
若
则有
* Catalan数
递推公式一
Catalan(0) = Catalan(1) = 1
Catalan(n) = Catalan0) ∗ Catalan(n−1) + Catalan(1) ∗ Catalan(n−2)+...+Catalan(n−1) ∗ Catalan(0)(n >= 2)
递推公式二
Catalan(n) = Catalan(n−1) ∗ (4 ∗ n − 2) / (n + 1)
组合数公式一
Catalan(n) = C(2n, n) / (n + 1) (n = 0, 1, 2,...
组合数公式二
Catalan(n) = C(2n, n) − C(2n, n − 1) (n = 0, 1, 2,..
* Lucas定理
Lucas(n, m, p) = C(n % p, m % p) * Lucas(n / p, m / p, p)。
* 中国剩余定理
设 m1, m2, ...,mn 是两两互质的整数,m = ∏mi ,Mi = m / mi ,ti 是线性同余方程的一个解。
对于任意的 n 个整数 a1, a2, ...,an,方程组
有整数解,解为。