====== 欧拉函数 ======

=== 定义 ===

$1\sim N$ 中与 $N$ 互质的数的个数叫欧拉函数, 记为 $\varphi(N)$

对 $N$ 分解质因数 $N=p_1^{c_1}\times p_2^{c_2}\times\cdots\times p_k^{c_k}$

特别地, $\varphi(1)=1$

=== 性质 ===

  - $\varphi(N)=N\times(1-\frac{1}{p_1})\times(1-\frac{1}{p_2})\times\cdots\times(1-\frac{1}{p_k})$
  - 若有 $p\ |\ N$, 且满足 $p^2\ |\ N$, 则 $\varphi(N)=\varphi(N/p)*p$
  - 若有 $p\ |\ N$, 且一定不满足 $p^2\ |\ N$, 则 $\varphi(N)=\varphi(N/p)*(p-1)$
  - $\forall N>1, 1\sim N$ 中与 $N$ 互质的数的和为 $N*\varphi(N)/2$
  - 当 $a,b$ 互质时, 有 $\varphi(a*b)=\varphi(a)*\varphi(b)$
  - 对 $N$ 分解质因数 $N=p_1^{c_1}\times p_2^{c_2}\times\cdots\times p_k^{c_k}$, 则有 $\varphi(N)=\prod_{i=1}^{k}\varphi(p_i^{c_i})$
  - $\varphi(p^k)=p^k-p^{k-1}$
  - $\sum_{d|n}\varphi(d)=n$
  - 若正整数 $a, n$ 互质, 则有 $a^{\varphi(n)}\equiv1\pmod{n}$
  - 若正整数 $a, n$ 互质, 则对于任意正整数 $b$, 有 $a^b\equiv a^{b\ mod\ \varphi(n)}\pmod{n}$
  - $a, n\in N$, 则$a^b\equiv \left\{\begin{array}{rl}a^b\pmod{n}&,b<\varphi(n),\\a^{b\ mod\ \varphi(n)+\varphi(n)}\pmod{n}&,b\ge\varphi(n). \end{array} \right.$
  - 若 $gcd(m,n)=d$, 则 $\varphi(mn)=d\varphi(m)\varphi(n)/\varphi(d)$
  - 若 $m\ |\ n$, 则 $\varphi(mn)=m\varphi(n)$
  - 若 $m\ |\ n$, 则 $\varphi(m)|\varphi(n)$
  - $\varphi(n)=\sum_{d|n}d\cdot\mu(\frac n d)$

=== 参考资料 ===

[[https://blog.csdn.net/niiick/article/details/81347041|]]

[[https://www.cnblogs.com/BlueHeart0621/p/11706153.html|]]