经常忘记的数学定理~

$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$$

爱我所爱,行我所行,听从我心,无问西东。