Eulerのトーシェント函数
Euler*1のトーシェント函数*2とは主に と表記される、整数論における函数です。次のように定義されます。
$$
\varphi(n) = \#\{k \mid 1 \leq k \leq n,\ \gcd(n,\,k) = 1\}
$$
日本語で書くと から
までの整数のうち、
と互いに素な整数の個数となります。
今回は が有限の自然数からなる集合
を用い、
を
番目の素数として $$
n = \prod_{i \in S} {p_i}^{e_i}\hspace{2em} (\forall i \in S,\ e_i \geq 1)
$$ と素因数分解されるとき、
$$
\varphi(n) = \prod_{i \in S} ({p_i}^{e_i} - {p_i}^{e_i - 1}) = n \prod_{i \in S} \left( 1 - \frac{1}{p_i} \right)
$$
となることについて証明っぽいことをしていきます。
$n$ が素数の累乗のとき
のときで、
とすると
と書けます。
このとき $$
\varphi(n) = \varphi(p^k) = p^k - p^{k - 1} = p^{k - 1} (p - 1) = n \left( 1 - \frac{1}{p} \right)
$$ となります。
これは、 となるとき
は
の倍数であり、
から
の整数のうち、
の倍数であるのは
の
個であることから示せます。
乗法的という性質
1.
2.
また、1. の性質の という条件を省いた場合、すなわち
が互いに素であるかどうかに関わらず
が成立する場合、完全乗法的といいます。
トーシェント函数の乗法性
トーシェント函数の乗法的です。つまり、 と
を互いに素な2整数とすると
$$
\varphi(mn) = \varphi(m) \varphi(n)
$$ が成立します。これについては中国剰余定理を用いて証明します。
を
以上
以下の整数とし、
$$
x \equiv\left\{
\begin{array}{ll}
a & \pmod{m}\\
b & \pmod{n}
\end{array}
\right.
$$ とします。
と
が互いに素なとき
は
の両方と互いに素です。
中国剰余定理依り各 に対応する
はそれぞれ1つづつ存在します。このような
の写像は単射であり、両集合が同数の元を持つ有限集合であることから全単射となります。つまり、
と
は一対一対応します。
以上から から
までの整数で
と互いに素な整数の個数は
の元で
を満たすような
の個数であり、その個数は
となり、乗法性が示されました。
冒頭の公式
ここで冒頭の公式を証明できるようになりました。乗法的であることから
$$
\varphi(n) = \varphi\left(\prod_{i \in S} {p_i}^{e_i}\right) = \prod_{i \in S} \varphi \left( {p_i}^{e_i} \right)
$$
となり、各素因数について上の公式より
$$
\varphi(n) = \prod_{i \in S} \left( {p_i}^{e_i} - {p_i}^{e_i - 1} \right) = \prod_{i \in S} {p_i}^{e_i} \left(1 - \frac{1}{p_i} \right) = n \prod_{i \in S} \left( 1 - \frac{1}{p_i} \right)
$$
となり、斯く示されました。
