Euler Totient Function

\[ \phi (n) := \# \{ m \in \mathbb{N} | m \le n \; \text{and} \; (m,n)=1 \} \]

Euler function은 n보다 작거나 같은 서로소의 개수에 대한 함수이다.

Theorem 1.

\[ \phi (n) = n \prod _{p|d} \left( 1 - \frac {1}{p} \right) \]

소인수분해를 한 후 포함과 배제의 원리를 적용하여 직접 함수값을 추론하면 된다.

\[ \mathrm{for} \; n=1, \quad \phi(1) = 1, \quad \mathrm{True} \]

\[ \mathrm{for} \; n>1, \; \mathrm{Let \ standard  \ prime \  factorization \; } n= p_1 ^{a_1} p_2 ^{a_2} \cdots p_k ^{a_k} \]

\[ \phi (n) = n \left( 1 - \sum \frac {1}{p_i } + \sum \frac {1}{p_i p_j} - \cdots + \frac {(-1)^k}{p_1 p_2\cdots p_r }  \right) \\ = n \prod _{i=1} ^k \left( 1 - \frac {1}{p_i} \right) = n \prod _{p|n} \left( 1 - \frac {1}{p} \right) \]

Theorem 2. \(\phi \)는 multiplicative function이다.

\[ \mathrm{for} \quad p \in \mathbb{P} , \; a \in \mathbb{N} , \quad \mathrm{consider} \quad p^a \; : \;  \phi (p^a) = p^a - p^{a-1} \]

\[ \mathrm{for \ standard \ prime \ factorization  \; } n = p_1 ^{a_1} p_2 ^{a_2} \cdots p_k ^{a_k} \]

\[ \phi (n) = n \prod _{p \in \{ p_1,p_2,\cdots,p_k\} } \left( 1- \frac {1}{p} \right) = \prod _{i=1} ^k {p_i}^{a_i} \left( 1 - \frac {1}{p_i } \right) = \prod _{i=1} ^k \phi (p_i ^{a_i} ) \]

이제 \( \phi (mn) = \phi (m) \phi (n) \quad \forall (m,n) =1 \)임은 각각을 소인수분해하여 쉽게 증명할 수 있을 것이다.