Carmichael函数はEulerのトーシェント函数の約数

Carmichael*1 函数はCarmichaelの定理に出てくる函数ですが、逆にこれ以外では出てこないと思います。しかし、定義が少し煩雑であるのと、この函数が返す値がEuler*2のトーシェント函数の与える値の約数になっていることについての証明をしたいので1つの記事にしています。

定義
$ 1 $ の時
$ 2 $ の累乗の時
奇素数の累乗の時
素因数が2種類以上ある場合

定義

Carmichael函数 $\lambda(n)$ の定義は少し煩雑なものになっています。
$n = 2^e\hspace{1em} (e \in \mathbb{N}^{+})$ のときは

$\lambda(2^e) = \left\{ \begin{array}{ll} 1 &(e = 1)\\ 2 &(e = 2)\\ 2^{e-2} &(e \geq 3)\\ \end{array} \right.$

となります。
$n = p^e\hspace{1em} (p\ は奇素数,\ e \in \mathbb{N}^{+})$ のときは

$\lambda(p^e) = p^{e-1} (p-1)$

となります。

また、 $n$ が有限の自然数からなる集合 $S$ を用い、 $p_i$ を $i$ 番目の素数として $$
n = \prod_{i \in S} {p_i}^{e_i}\hspace{2em} (\forall i \in S,\ e_i \geq 1)
$$ と素因数分解されるとき、

$\displaystyle \lambda\left(\prod_{i \in S} {p_i}^{e_i}\right) = \underset{i \in S}{\mathrm{lcm}}\, \lambda({p_i}^{e_i})$

となります。 $\mathrm{lcm}$ は最小公倍数(Least Common Multiple)です。

$n = 1$ の場合は素因数がないため上の定義とは異なり個別に $\lambda(1) = 1$ と定義されています*3。

さて、ここからは題名の通りCarmichael函数はEulerのトーシェント函数の約数であることを証明していきます。といっても結構簡単なものです。

$ 1 $ の時

$\lambda(1) = \varphi(1) = 1$ より成立します。

$ 2 $ の累乗の時

$\varphi(2^e) = 2^{e-1}(2-1) = 2^{e-1}$ であるため上の定義から

$\varphi(2^e) = \left\{ \begin{array}{ll} \lambda(2^e) &(e = 1,\,2)\\ 2\lambda(2^e) &(e \geq 3)\\ \end{array} \right.$

であるため、この場合ちゃんと倍数となっています。

奇素数の累乗の時

$\varphi(p^e) = p^{e-1}(p-1) = \lambda(p^e)$ です。

素因数が2種類以上ある場合

上の通り $\displaystyle n = \prod_{i \in S} {p_i}^{e_i}\hspace{1em} (\forall i \in S,\ e_i \geq 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)$ は各 $\varphi ( {p_i}^{e_i} )$ の積であるため、その倍数です。それぞれの $\varphi ( {p_i}^{e_i} )$ は対応する $\lambda({p_i}^{e_i})$ の倍数であり、 $\lambda(n)$ はそれらの最小公倍数であるため、 $\varphi(n)$ は $\lambda(n)$ の倍数となり、示すべきことが示せました。