经常忘记的数学定理~
$n!$的质因数分解定理
定理:对于小于$n$的质数$p$，$n!$中含有因子$p$的个数为:
$$n/p+n/p^2+…+n/p^k(其中k为p^k<=n的最大值)$$
约数和
对于一个数$N$，如果它的标准分解式为
$$N=p_1^{a_1}p_2^{a_2}p_3^{a_3}…p_n^{a_n}$$
那么约数和为
$$S=\prod_{i=1}^n\sum_{j=0}^{a_i}p_i^j(p_1,p_2……p_n为质数)$$
那么约数个数为
$$S=\prod_{i=1}^n(a_i+1)$$
威尔逊定理
当且仅当$p$是素数时
$$(p-1)! \equiv p-1(\mod p)$$
考虑如果这$p-1$个数中如果一个数是一个数的逆元那么这两个数都会被消去，留下的都是逆元是本身的数。
若一个数的逆元等于本身，则有
$$x \equiv x^{-1} ( \mod p)$$
那么两边平方，移项，则有
$$x^2 \equiv 1 ( \mod p)$$
$$x^2-1\equiv 0 ( \mod p)$$
$$(x+1)(x-1) \equiv 0 ( \mod p)$$
所以$p|(x+1)(x-1)$，由于$p$是质数，所以$x$只能是$1$或$p-1$。
$$Q.E.D.$$
判断两个大数相等
选取适当个大质数，如果两个数$mod$选取的所有的质数都相等则两个大数有很大概率相等。
勾股数组
勾股方程即形如$a^2+b^2=c^2$的方程。
勾股方程的所有正整数解都可以被表示为下图的形式
$$a=\frac{d(u^2-v^2)}{2},b=duv,c=\frac{d(u^2+v^2)}{2}(gcd(u,v)=1)$$
不明定理
$$(\sum_{i=1}^n i)^2=\sum_{i=1}^n i^3$$
