オイラーのトーシェント関数，メビウスの関数，メモ書き
オイラーのトーシェント関数や，メビウスの関数について，今日までに勉強したことの一部のメモ書きです．
オイラーのトーシェント関数
オイラーのトーシェント関数
オイラーのトーシェント関数 \varphi(n)は正の整数から正の整数への関数．正の整数 n に関して，1から n のうち，n と互いに素である数の個数を返す．
（例）
\varphi(1) = 1
\varphi(2) = 1
\varphi(3) = 2
\varphi(4) = 2
\varphi(5) = 4
\varphi(6) = 2
素数 n に関しては \varphi(n) = n - 1 となる．
オイラーのトーシェント関数に関する定理
互いに素な n,m に対して， \varphi(mn) = \varphi(m) \varphi(n) が成り立つ．
定理．
素数 p に関して，
\begin{aligned} \varphi(p^k) = p^k \left(1 - \frac{1}{p} \right) \end{aligned}
証明．
\begin{aligned}
\varphi(p^k) &= p^k - p^{k-1} \\
&= p^k \left(1 - \frac{1}{p} \right)
\end{aligned}
メビウスの関数
メビウスの関数(Möbius function)1Möbiusでメビウスと読むことがひとつの学びだった．とは，0を除く自然数 n に対して定義される関数 \mu (n) であり，素数の平方数で割り切れると \mu (n) = 0 となり，それ以外の場合は，素因数の数が k のとき， \mu (n) = (-1)^{k} となる関数である．
メビウスの関数(Möbius function)
メビウスの関数 \mu は \mu : 0を除く自然数 \to {-1, 0, 1}
0を除く自然数 n が素数の平方数で割り切れる場合
\mu (n) = 0
それ以外の場合， n の相違なる素因数の総数を k とすると，
\mu (n) = (-1)^{k}
ただし， \mu (1) = 1 とする．
（例）
\mu (2) = -1
\mu (3) = -1
\mu (4) = 0
\mu (5) = -1
\mu (6) = 1
メビウスの関数に関する定理
互いに素なm, n に関して\mu (m) \mu (n) = \mu (mn)
m, n が互いに素でなければ，\mu (m) \mu (n) = 0
共通する素因数を持つ→その素数の平方数で割りきれるため．
定理．
n \leq 2 の自然数に関して \sum_{d | n} \mu (d) = 0
つまり，n の全ての正の約数 d に関して，\mu (d) を足し合わせると0になる．
証明．
n の素因数をp_1 , p_2, \cdots p_kとする．同じ素因数を2つ以上掛けた約数に関しては，\mu (d) = 0 となるため，考える必要がない．よって，p_1 , p_2, \cdots p_kの素因数の中から1〜k種類の素因数を1つずつ掛けてできる約数のみを考えれば良いので，
\sum_{d | n} \mu (d) \\
= 1 - {}_k C_1 + {}_k C_2 + \cdots \cdots + (-1)^k {}_k C_k \\
= \sum_{r=0}^{k} (-1)^r {}_k C_r \\
= (1-1)^k \\
=0
二項定理を使って証明している．
