오일러의 토션트 합 공식 유도

오일러의 토션트 합 공식 유도

공식

$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$ 임을 보이면 된다.


Case 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*} $$


Case 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*} $$


Case 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$ 이 성립한다.

댓글