オイラー関数
a.k.a.
$ \phi(n) は$ [1, n] の範囲の$ nと互いに素な自然数の個数を返す関数 $ \phi(n)=n\prod_{p|n}\left(1-\frac1p\right)
導出
1. $ [1,p^{w_p}] の範囲の$ p^{w_p}と互いに素な自然数は$ p^{w_p}\left(1-\frac1p\right)個 $ p^{w_p}\left(1-\frac1p\right)=p^{w_p}-p^{w_p-1}
$ [1,p^{w_p}] の範囲の$ pの倍数は$ p^{w_p-1}個のため
$ 1p,2p,3p,\cdots,p^{e_w-1}pの$ p^{w_p-1}個ある
2. $ \phi(n)=n\prod_{p|n}\left(1-\frac1p\right)
$ n\prod_{p|n}\left(1-\frac1p\right)=\prod_{p|n}p^{w_p}\left(1-\frac1p\right)
$ n=\prod_{p|n}p^{w_p}
$ \begin{cases}c\overset m\equiv a\\c\overset n\equiv b\end{cases}を満たす$ (a,b)\in(\Z/m\Z,\Z,n\Z)と$ c\in(\Z/mn\Z)を結ぶ全単射が存在 $ (m,a)\in{\rm\mathcal Cop},$ (n,b)\in{\rm\mathcal Cop}とすると
$ \begin{cases}c\overset m\equiv a\\c\overset n\equiv b\end{cases}を満たす$ (a,b)と$ c\quad(\gcd(c,mn)=1)を結ぶ全単射が存在 1 対 1 対応なので$ cの個数は$ \phi(mn)=\phi(m)\phi(n)
$ (m,a)\in{\rm\mathcal Cop}を満たす$ aが$ \phi(m)個存在
$ (n,b)\in\rm{\rm\mathcal Cop}を満たす$ bが$ \phi(n)個存在
$ (mn,c)\in{\rm\mathcal Cop}を満たす$ cが$ \phi(mn)個存在
これらは$ (a,b)\leftrightarrow cの対応を付けられるので$ \phi(m)\phi(n)個存在
$ \therefore\phi(mn)=\phi(m)\phi(n)