オイラーのトーシェント関数
(オイラーのトーシェント関数についての軽いメモです.)
本記事では, 圏論的概念である随伴関手の性質を用いることで, オイラーのトーシェント関数の性質を明らかにする.
自然数$\mathbb N$は, この記事では正の整数全体の集合とする.
$\varphi:\mathbb N\to\mathbb N$を, 任意の$n\in\mathbb N$に対して
\begin{align}
\varphi(n):=\Big|(\mathbb Z/n\mathbb Z)^×\Big|
\end{align}
と定義する. これをオイラーのトーシェント関数(Euler's totient function), またはオイラーの$\varphi$関数(phi function)という.
$n\in\mathbb N$に対して$\varphi(n)$は, $n$と互いに素な, $n$以下の自然数の個数を意味する(赤雪江参照yukie1).
$12$と互いに素な, $12$以下の自然数は$1,5,7,11$なので
\begin{align}
\varphi(12)=4.
\end{align}
この記事は, 定理1の$\varphi$の明示的な表示を, 2つの命題に分けて証明する.
\begin{align} \varphi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right). \end{align}
\begin{align} \varphi(12)&=12\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\\ &=2(2-1)(3-1)\\ &=4. \end{align}
単数群関手$(-)^×$の随伴性より, $\varphi$は以下のように$p$べきに分解できる.
$\mathbb N\ni n=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}$($p_1,p_2,\dots,p_m$はすべて異なる素数)とすると,
\begin{align}
\varphi(n)=\prod_{i=1}^m \varphi(p_i^{k_i})
\end{align}
単数群関手は群環関手の右随伴である, つまり$\mathbb Z[-]\dashv(-)^×:\mathbf{Ab}\to\mathbf{CRing}$(これを示すにはunit, counitを具体的に構成すればよい). よって単数群関手は極限と交換する. 特に, 直積と交換する. そのことを踏まえて中国剰余定理とあわせると, 以下を得る.
\begin{align}
(\mathbb Z/n\mathbb Z)^×&\cong \left(\prod_{i=1}^m\mathbb Z/p_i^{k_i}\mathbb Z\right)^×\\
&\cong \prod_{i=1}^m(\mathbb Z/p_i^{k_i}\mathbb Z)^×.
\end{align}
よって両辺の位数を比較すれば主張が示される.
あとは$p$べきに関して$\varphi$を調べればよい.
$p$を素数として,
\begin{align}
\varphi(p^k)=p^k\cdot\left(1-\frac{1}{p}\right)
\end{align}
$\mathbb Z/p^k\mathbb Z$の単元は$p^k$と互いに素である. よって$\mathbb Z/p^k\mathbb Z$の単元でないものは$p$の倍数で, 個数は$p^k/p=p^{k-1}$. $\mathbb Z/p^k\mathbb Z$の位数は$p^k$であるので, 以下を得る.
\begin{align}
\Big|(\mathbb Z/p^k\mathbb Z)^×\Big|&=p^k-p^{k-1}\\
&=p^k\left(1-\frac{1}{p}\right).
\end{align}
以上より, 任意の$n\in\mathbb N$に対して
\begin{align}
\varphi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)
\end{align}
と書くことができる.
