[备忘] 数学小定理相关
写在前面
由于上一篇数学相关分版块记录定理及证明，对于小定理等略有繁琐，故新开一篇博客记录一些数学小芝士，以此备忘。
一个整数 \(N\) 的约数个数上界为 \(2\sqrt N\)。
\(1-2\times 10^9\) 中任何数的不同质因子都不会超过 \(10\) 个，且所有质因子的指数总和不超过 \(30\)。
证明：因为最小的 \(11\) \(2\times 3\times 5\times 7\times 11\imes 13\times 17\times 19\times 23\times 29\times 31>2\times 10^9\)，所以 \(N\leq 2\times 10^9\) 不可能有多于 \(10\) 个不同质因子。
因为即使只包含最小的质数，仍然有 \(2^{31}>2\times 10^9\) ，所以 \(N\leq 2\times 10^9\) 的质因子质数总和不会超过 \(30\)。
\[\sum _{d\mid n}\phi(d)=n\]
\[gcd(a,n)=1\Rightarrow a^{\phi(n)}\equiv 1\quad (mod\;n)\Rightarrow a^b\equiv a^{b\;mod\;\phi(n)}\quad (mod\;n)\]
若 \((a,n)=1\)，则满足 \(a^x\equiv 1\quad (mod\;n)\) 的最小正整数 \(x_0\) 是 \(\phi(n)\) 的约数。
版权声明：本文为YoungNeal原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。