📂整数論

オイラーのトーシェント合計式の導出

公式

$n$ の 約数を $d_{1}, d_{2} , \cdots , d_{r}$ とすると、 $$n = \sum_{ i = 1 }^{r} \phi (d_{i}) = \phi (d_{1}) + \phi (d_{2}) + \cdots + \phi (d_{r})$$

説明

トーシェント関数は定義されてから少し不自然に感じられるかもしれない。しかし、オイラーのファイ関数定理などこのような公式を見ると、数学の真理のどこかで明確に必要な関数であると認めざるを得ない。

例えば、$15$ に対して、$15$ は約数 $1,3,5,15$ を持つ。実際に計算してみると、次のようになる。 $$\begin{align*} \phi (1) + \phi (3) + \phi (5) + \phi (15) =& \phi (1) + \phi (3) + \phi (5) + \phi (3) \phi (5) \\ =& 1 + 2 + 4 + 2 \cdot 4 \\ =& 15 \end{align*}$$

導出

$F(n) := \phi (d_{1}) + \phi (d_{2}) + \cdots + \phi (d_{r})$ と定義し、$F(n) = n$ が成立することを示す。

---

ケース 1. $n$ が 素数

素数 $p$ のべき乗 $n = p^{k}$ の場合、 $$\begin{align*} F(n) =& \phi (1) + \phi (p) + \cdots \phi (p^{k}) \\ =& 1 + (p-1) + \cdots + (p^{k} - p^{k-1}) \\ =& p^{k} \end{align*}$$

---

ケース 2. $n$ が二つの素数 $p,q$ のべき乗の積

$n = p^{k_{p}} q^{k_{q}}$ とすると、 $$\begin{align*} F(n) =& \phi (1) + \phi (p) + \cdots + \phi (p^{k_{p}}) + \phi (q) + \cdots + \phi (q^{k_{q}}) \\ & + \phi (pq) + \phi (p^{2}q) + \phi (pq^{2}) + \cdots + \phi (p^{k_{p}} q^{k_{q}}) \end{align*}$$ トーシェント関数の乗法的性質により、 $$\begin{align*} F(n) =& \phi (1) + \phi (p) + \cdots \phi (p^{k_{p}}) + \phi (q) + \cdots \phi (q^{k_{q}}) \\ & + \phi (p) \phi (q) + \phi (p^{2}) \phi (q) + \phi (p) \phi (q^{2}) + \cdots \phi (p^{k_{p}}) \phi ( q^{k_{q}}) \\ =& \left[ \phi (1) + \phi (p) + \cdots \phi (p^{k_{p}}) \right] \left[ 1 + \phi (q) + \cdots \phi (q^{k_{q}}) \right] \\ =& F(p^{k_{p}}) F(q^{k_{q}}) \end{align*}$$

---

ケース 3. $n$ が任意の自然数

算術の基本定理により、$n = p_{1}^{k_{1}} p_{2}^{k_{2}} \cdots p_{s}^{k_{s}}$ と表せる。 $$\begin{align*} F(n) =& F(p_{1}^{k_{1}}) F(p_{2}^{k_{2}}) \cdots F(p_{s}^{k_{s}}) \\ =& p_{1}^{k_{1}} p_{2}^{k_{2}} \cdots p_{s}^{k_{s}} \\ =& n \end{align*}$$ したがって、どの場合でも $F(n) = n$ が成立する。

■