オイラー関数

Euler's totient function

$ \{1,\cdots,N-1\}のうち、$ Nと互いに素な数の個数を$ \phi(N)で表す

この$ \phiがオイラー関数

$ \varphi(n)=|\mathbb{Z}^\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