欧拉定理
# 欧拉定理
$gcd(a, n) = 1$ => $a^{\phi(n)} \equiv 1 \pmod{n}$
# 欧拉 $\phi()$ 函数
欧拉 Phi 函数 $\phi$ 对任意正整数 n,返回 1 到 n 之间且与 n 互素的整数个数
$\phi(mn) = \phi(m) \phi(n)$ m, n is prime
$\phi(p) = p-1$
$\phi(p^{k}) = p^{k} - p^{k-1}$
$gcd(a, n) = 1$ => $a^{\phi(n)} \equiv 1 \pmod{n}$
欧拉 Phi 函数 $\phi$ 对任意正整数 n,返回 1 到 n 之间且与 n 互素的整数个数
$\phi(mn) = \phi(m) \phi(n)$ m, n is prime
$\phi(p) = p-1$
$\phi(p^{k}) = p^{k} - p^{k-1}$