初等整数論 (7)Eulerの関数
写像$~\varphi:\mathbb{Z}\to\mathbb{N}~$を$~\varphi(m):=|(\mathbb{Z}/m\mathbb{Z})^{\times}|~$で定める。
この写像$~\varphi~$をEulerの$\varphi$関数(または単にEulerの関数)という。
$m\gt0~$の場合に限れば、$\varphi(m)~$は「$~0~$以上$~m~$未満の$~m~$と互いに素な整数の個数」という意味をもつ。
しかし、$m\mathbb{Z}=(-m)\mathbb{Z}~$なので$~\varphi(m)=\varphi(-m)~$となり、「$~0~$以上$~|m|~$未満の$~m~$と互いに素な整数の個数」とすれば$~m\in\mathbb{Z}\setminus\{0\}~$に対してはこの意味で解釈できる。
$m=0~$に関しては$~\mathbb{Z}/(0)\simeq\mathbb{Z}~$なので、$\varphi(0)=|(\mathbb{Z}/(0))^{\times}|=|\mathbb{Z}^{\times}|=|\{1,-1\}|=2~$となる。
定理21
素数$~p\in\mathbb{Z}~$に対して、$\varphi(p)=p-1~$となる。また、正整数$~e~$に対して$~\varphi(p^e)=p^{e-1}(p-1)~$である。
$\mathbb{Z}/p\mathbb{Z}~$は体なので$~(\mathbb{Z}/p\mathbb{Z})^{\times}=(\mathbb{Z}/p\mathbb{Z})\setminus\{\overline{0}\}~$である。
よって、$\varphi(p)=|(\mathbb{Z}/p\mathbb{Z})^{\times}|=|(\mathbb{Z}/p\mathbb{Z})\setminus\{\overline{0}\}|=p-1~$となる。
$p^e~$は素因数として$~p~$しかもたないので、$p^e~$と互いに素でない$~1~$より大きい整数は$~p~$を素因数としてもつ。
よって、$0~$以上$~p^e~$未満で$~p^e~$と互いに素でない整数は \[ 1, p, 2p, \dots, (p^{e-1}-1)p=p^e-p \] の$~p^{e-1}~$個である。
よって、$\varphi(p^e)=p^e-p^{e-1}=p^{e-1}(p-1)~$となる。
$$\square$$
よって、$\varphi(p)=|(\mathbb{Z}/p\mathbb{Z})^{\times}|=|(\mathbb{Z}/p\mathbb{Z})\setminus\{\overline{0}\}|=p-1~$となる。
$p^e~$は素因数として$~p~$しかもたないので、$p^e~$と互いに素でない$~1~$より大きい整数は$~p~$を素因数としてもつ。
よって、$0~$以上$~p^e~$未満で$~p^e~$と互いに素でない整数は \[ 1, p, 2p, \dots, (p^{e-1}-1)p=p^e-p \] の$~p^{e-1}~$個である。
よって、$\varphi(p^e)=p^e-p^{e-1}=p^{e-1}(p-1)~$となる。
定理22
$m_1,\dots,m_n\in\mathbb{Z}~$をどの2つも互いに素な整数とし、$m=m_1\cdots m_n~$とおく。このとき、次が成り立つ。 \[ \varphi(m)=\varphi(m_1)\cdots\varphi(m_n) \]
$(\mathbb{Z}/m\mathbb{Z})^{\times} \simeq (\mathbb{Z}/m_1\mathbb{Z})^{\times}\times\cdots\times(\mathbb{Z}/m_n\mathbb{Z})^{\times}~$より明らか。
$$\square$$
定理23
正整数$~m\in\mathbb{Z}_{\gt}~$を相異なる素数$~p_1,\dots,p_n~$によって、
\[
m = {p_1}^{e_1}\cdots{p_n}^{e_n}
\]
と素因数分解できたとき、次が成り立つ。
\[
\varphi(m) = \prod_{i=1}^{n}p_i^{e_i-1}(p_i-1)
\]
$p_1,\dots,p_n~$はどの2つも相異なるので、どの2つも互いに素である。
よって、${p_1}^{e_1},\dots,{p_n}^{e_n}~$はどの2つも互いに素となる。
したがって、定理22より \[ \varphi(m) = \varphi({p_1}^{e_1})\cdots\varphi({p_n}^{e_n}) = {p_1}^{e_1-1}(p_1-1)\cdots{p_n}^{e_n-1}(p_n-1) \] となる。
$$\square$$
よって、${p_1}^{e_1},\dots,{p_n}^{e_n}~$はどの2つも互いに素となる。
したがって、定理22より \[ \varphi(m) = \varphi({p_1}^{e_1})\cdots\varphi({p_n}^{e_n}) = {p_1}^{e_1-1}(p_1-1)\cdots{p_n}^{e_n-1}(p_n-1) \] となる。