📂정수론

토션트 함수

같이보기

• 해석적 정수론에서의 토션트 함수

정의 ¹

다음과 같이 정의된 $\phi$ 를 오일러 토션트 함수라 한다.

$$\phi ( m ) := \left| \left\{ a \ | \ 1 \le a \le m \land \gcd (a,m) = 1 \right\} \right| = m \prod_{p \mid m} \left( 1 - {{1} \over {p}} \right)$$

설명

토션트^totient는 전체를 의미하는 Tot-al의 Tot-과 몫을 의미하는 Quo-tient에서 -tient가 붙어서 생긴 단어로 이해해도 무방하다. 수학, 그것도 정수론 외에는 전혀 쓰이지 않을뿐만 아니라 그조차도 파이Phi 함수 혹은 피Phi 함수 로 쓰는 경우가 많은 편이다.

$1$ 부터 $10$ 정도까진 직접 계산해서 감을 잡아보자. $$\begin{align*} \phi ( 1 ) = & \left| \left\{ 1 \right\} \right| = 1 =1 \\ \phi ( 2 ) = & \left| \left\{ 1 \right\} \right| = 2 {{1} \over {2}} = 1 \\ \phi ( 3 ) = & \left| \left\{ 1 , 2 \right\} \right| = 3 {{2} \over {3}} = 2 \\ \phi ( 4 ) = & \left| \left\{ 1 , 3 \right\} \right| = 4 {{1} \over {2}} = 2 \\ \phi ( 5 ) = & \left| \left\{ 1 , 2 , 3 , 4 \right\} \right| = 5 {{4} \over {5}} = 4 \\ \phi ( 6 ) = & \left| \left\{ 1 , 5 \right\} \right| = 6 {{1} \over {2}} {{2} \over {3}} = 2 \\ \phi ( 7 ) = & \left| \left\{ 1 , 2 , 3 , 4 , 5 , 6 \right\} \right| = 7 {{6} \over {7}} = 6 \\ \phi ( 8 ) = & \left| \left\{ 1 , 3 , 5 , 7 \right\} \right| = 8 {{1} \over {2}} = 4 \\ \phi ( 9 ) = & \left| \left\{ 1 , 2, 4 , 5 , 7, 8, \right\} \right| = 9 {{2} \over {3}} = 6 \\ \phi ( 10 ) = & \left| \left\{ 1 , 3 , 7 , 9 \right\} \right| = 10 {{1} \over {2}} {{4} \over {5}} = 4 \end{align*}$$

언뜻 왜 이렇게 계산하기 어렵고 규칙 없어 보이는 함수가 왜 필요한지 궁금할 수 있다. 알고보면 아름다운 성질들을 풍부하게 갖고 있을 뿐만 아니라 여러가지 이론을 지탱하는 토대가 됨을 알 수 있을 것이다.

정리

소수 $p$ 에 대해, $\phi (p^{k}) = p^{k} - p^{k-1}$

증명

전략: 소수의 거듭제곱에 대한 함숫값은 카운팅을 통해 쉽게 구할 수 있다.

---

$p$ 가 소수이므로, 임의의 $n \in \mathbb{N}$ 에 대해 $\gcd (p, np) \ne 1$ 즉 $$p , 2p , \cdots (p^{k-1} - 2 ) p , (p^{k-1} - 1 ) p , p^{k} \notin \left\{ a \ | \ 1 \le a \le p^{k} \land \gcd (a,p^{k}) = 1 \right\}$$ 이들은 정확하게 $p^{k-1}$ 개 존재하므로, $\phi (p^{k}) = p^{k} - p^{k-1}$

■