オイラーのトーシェント関数の性質
オイラーのトーシェント関数の性質
オイラーのトーシェント関数\(\phi\left(x\right)\)は次の性質を満たす。
\[ \phi\left(n\right)=n\prod_{k=1}^{d}\left(1-\frac{1}{p_{k}}\right) \]
オイラーのトーシェント関数\(\phi\left(x\right)\)は次の性質を満たす。
(1)
\(p\)が素数なら\(\phi\left(p\right)=p-1\)が成り立つ。\(n\)を自然数とすると\(\phi\left(p^{n}\right)=p^{n}-p^{n-1}\)が成り立つ(2)
\(\gcd\left(m,n\right)=1\)のとき\(\phi\left(mn\right)=\phi\left(m\right)\phi\left(n\right)\)(3)
\[ n=\prod_{k=1}^{d}p_{k}^{e_{k}} \] のとき、\[ \phi\left(n\right)=n\prod_{k=1}^{d}\left(1-\frac{1}{p_{k}}\right) \]
(4)
\[ \sum_{d\mid n}\phi\left(d\right)=n \](1)
\(p\)が素数なので\(1\)以上\(p-1\)以下の数は全て\(p\)と互いに素なので\(\phi\left(p\right)=p-1\)となる。また\(1\)以上\(p^{n}\)以下の数字で\(p^{n}\)と素でないものは\(p\)を因子として含むものだけである。
\(p\)を因子と含むものは\(p\)の倍数なので\(p^{n-1}\)個あり、\(\phi\left(p^{n}\right)=p^{n}-p^{n-1}\)となる。
(2)
\(a\overset{mn}{\equiv}b\)ならば\(a\overset{m}{\equiv}b\land a\overset{n}{\equiv}b\)が成り立つので、\[ a+mn\mathbb{Z}=b+mn\mathbb{Z}\Rightarrow\left(a+m\mathbb{Z},a+n\mathbb{Z}\right)=\left(b+m\mathbb{Z},b+n\mathbb{Z}\right) \] が成り立つ。
ここで、写像\(f:\mathbb{Z}/mn\mathbb{Z}\rightarrow\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z},a+mn\mathbb{Z}\mapsto\left(a+m\mathbb{Z},a+n\mathbb{Z}\right)\)を考え\(f\)が全単射になることを示す。
単射であることを示す。
\(\left(a+m\mathbb{Z},a+n\mathbb{Z}\right)=\left(b+m\mathbb{Z},b+n\mathbb{Z}\right)\)であるとき、\(\left(a+m\mathbb{Z}=b+m\mathbb{Z}\right)\land\left(a+n\mathbb{Z}=b+n\mathbb{Z}\right)\)となり、\(-a+b\in m\mathbb{Z},-a+b\in n\mathbb{Z}\)となるので、\(a\overset{m}{\equiv}b\land a\overset{n}{\equiv}b\)となる。
このとき、\(\gcd\left(m,n\right)=1\)なので、\(a\overset{m}{\equiv}b\land a\overset{n}{\equiv}b\Leftrightarrow a\overset{mn}{\equiv}b\Leftrightarrow a+mn\mathbb{Z}=b+mn\mathbb{Z}\)となる。
従って\(f\)は単射となる。
次に全射であることを示す。
任意の\(\left(b+m\mathbb{Z},c+n\mathbb{Z}\right)\in\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}\)について、ある元\(a+m\mathbb{Z}\in\mathbb{Z}/mn\mathbb{Z}\)が存在して、\(\left(a+m\mathbb{Z},a+n\mathbb{Z}\right)=f\left(a+m\mathbb{Z}\right)=\left(b+m\mathbb{Z},c+n\mathbb{Z}\right)\)となることを示せばよい。
これは、
\begin{align*} \begin{cases} a+m\mathbb{Z}=b+m\mathbb{Z}\\ a+n\mathbb{Z}=c+n\mathbb{Z} \end{cases} & \Leftrightarrow\begin{cases} a\overset{m}{\equiv}b\\ a\overset{n}{\equiv}c \end{cases} \end{align*} となり、\(\gcd\left(m,n\right)=1\)なので中国剰余定理より、\(mn\)を法として\(a\)は解をもつ。
従って、\(f\)は全射となる。
これらより、\(f\)は全単射となるので、
\begin{align*} \phi\left(mn\right) & =\left|\mathbb{Z}/mn\mathbb{Z}\right|\\ & =\left|\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}\right|\\ & =\left|\mathbb{Z}/m\mathbb{Z}\right|\left|\mathbb{Z}/n\mathbb{Z}\right|\\ & =\phi\left(m\right)\phi\left(n\right) \end{align*} となり題意は成り立つ。
(3)
\begin{align*} \phi\left(n\right) & =\phi\left(\prod_{k=1}^{d}p_{k}^{e_{k}}\right)\\ & =\prod_{k=1}^{d}\phi\left(p_{k}^{e_{k}}\right)\\ & =\prod_{k=1}^{d}\left(p_{k}^{e_{k}}-p_{k}^{e_{k}-1}\right)\\ & =\prod_{k=1}^{d}p_{k}^{e_{k}}\left(1-\frac{1}{p_{k}}\right)\\ & =n\prod_{k=1}^{d}\left(1-\frac{1}{p_{k}}\right) \end{align*}(4)
\(x\)を\(1\)以上\(n\)以下の自然数とする。\[ \gcd\left(x,n\right)=d\Longleftrightarrow\gcd\left(\frac{x}{d},\frac{n}{d}\right)=1 \] となるので、\(\gcd\left(x,n\right)=d\)となる\(x\)は\(\phi\left(\frac{n}{d}\right)\)個ある。
\(1\)以上\(n\)以下の自然数\(x\)は\(\gcd\left(x,n\right)\)の値\(d\)によって類別される。
\(d\)が\(n\)の約数全体を動くとき、\(1\)以上\(n\)以下の自然数は1度のみ必ず数えられるので、
\[ \sum_{d\mid n}\phi\left(\frac{n}{d}\right)=n \] となり、
\[ \sum_{d\mid n}\phi\left(\frac{n}{d}\right)=\sum_{d\mid n}\phi\left(d\right) \] となるので与式は成り立つ。
ページ情報
タイトル | オイラーのトーシェント関数の性質 |
URL | https://www.nomuramath.com/vjmeq9yp/ |
SNSボタン |
2元1次不定方程式の整数解とユークリッドの互除法
\[
ax+by=c
\]
2元1次不定方程式の性質
\[
ax+by=c\text{が整数解を持つ}\Leftrightarrow c\text{は}\gcd(a,b)\text{の倍数}
\]
n番目の素数の式
\[
P\left(n\right)=1+\sum_{k=1}^{2^{n}}\left\lfloor \sqrt[n]{\frac{n}{\sum_{j=1}^{k}\left\lfloor \cos^{2}\left(\frac{\left(j-1\right)!+1}{j}\pi\right)\right\rfloor }}\right\rfloor
\]
二元不定方程式が整数解を持つ
\[
ax+by=c\text{が整数解を持つ}\Leftrightarrow c\text{は}\gcd(a,b)\text{の倍数}
\]