(*)オイラーのトーシェント関数の性質
オイラーのトーシェント関数の性質
(1)
\(p\)が素数なら\(\varphi(p)=p-1\)が成り立つ。\(n\)を自然数とすると\(\varphi(p^{n})=p^{n}-p^{n-1}\)が成り立つ
(2)
\(\gcd(m,n)=1\)のとき\(\varphi(mn)=\varphi(m)\varphi(n)\)
(3)
\[ n=\prod_{k=1}^{d}p_{k}^{\;e_{k}} \]
のとき、
\[
\varphi(n)=n\prod_{k=1}^{d}\left(1-\frac{1}{p_{k}}\right)
\]
(4)
\[ \sum_{d\mid n}\varphi(d)=n \]
(1)
\(p\)が素数なので\(1\)以上\(p-1\)以下の数は全て\(p\)と互いに素なので\(\varphi(p)=p-1\)となる。
また\(1\)以上\(p^{n}\)以下の数字で\(p^{n}\)と素でないものは\(p\)を因子として含むものだけである。
\(p\)を因子と含むものは\(p\)の倍数なので\(p^{n-1}\text{個あり、}\varphi(p^{n})=p^{n}-p^{n-1}\)となる。
(2)
略
(3)
\begin{align*} \varphi(n) & =\varphi(\prod_{k=1}^{d}p_{k}^{\;e_{k}})\\ & =\prod_{k=1}^{d}\varphi(p_{k}^{\;e_{k}})\\ & =\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(x,n)=d\Longleftrightarrow\gcd\left(\frac{x}{d},\frac{n}{d}\right)=1 \]
となるので、\(\gcd(x,n)=d\)となる\(x\)は\(\varphi\left(\frac{n}{d}\right)\)個ある。
\(1\)以上\(n\)以下の自然数\(x\)は\(\gcd(x,n)\)の値\(d\)によって類別される。
\(d\)が\(n\)の約数全体を動くとき、\(1\)以上\(n\)以下の自然数は1度のみ必ず数えられるので、
\[
\sum_{d\mid n}\varphi\left(\frac{n}{d}\right)=n
\]
となり、
\[
\sum_{d\mid n}\varphi\left(\frac{n}{d}\right)=\sum_{d\mid n}\varphi\left(d\right)
\]
となるので与式は成り立つ。
ページ情報
タイトル | (*)オイラーのトーシェント関数の性質 |
URL | https://www.nomuramath.com/vjmeq9yp/ |
SNSボタン |