オイラー関数
Euler's totient function
\{1,\cdots,N-1\}のうち、Nと互いに素な数の個数を\phi(N)で表す
この\phiがオイラー関数
\varphi(n)=|\mathbb{Z}^\varphi_n|とも表せる
\mathbb{Z}^\varphi_nは1からnまでの整数でnと互いに素なものの集合
ex. \mathbb{Z}^\varphi_5=\{1,2,3,4\}
ex. \varphi(3)=\varphi(4)=\varphi(6)=2
公式集
素数pに対して
\varphi(p)=p-1
\varphi\left(p^{e}\right)=p^{e-1}(p-1)(e \in \mathbb{N})
m, n \in \mathbb{N}, \operatorname{gcd}(m, n)=1ならば\varphi(m n)=\varphi(m) \varphi(n)
n=p_{1}^{e_{1}} p_{2}^{e_{2}} \cdots p_{s}^{e_{s}}がnの素因数分解の時、
\varphi(n)=n\left(1-\frac{1}{p_{1}}\right)\left(1-\frac{1}{p_{2}}\right) \cdots\left(1-\frac{1}{p_{s}}\right)
p_iは素数、e_i\in \mathbb{N}
a^{-1}\equiv a^{\varphi(n)-1}\pmod n
a,b,n\in \mathbb{Z},n\geq2,\gcd(a,n)=1