欧拉定理

欧拉定理

$gcd(a,n)=1$ ⇒ $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$

欧拉 $\varphi ()$ 函数

欧拉 Phi 函数 $\varphi$ 对任意正整数 n,返回 1 到 n 之间且与 n 互素的整数个数

$\varphi (mn)=\varphi (m)\varphi (n)$ m, n is prime
$\varphi (p)=p-1$
$\varphi (p^k)=p^k-p^{k-1}$