📂정수론

토션트 함수의 곱셈적 성질 증명

정리 ¹

$$\gcd (n , m) =1 \implies \phi ( n m ) = \phi (n) \phi (m)$$

설명

토션트 함수에서 유도되는 여러가지 중요한 결과를 얻기 위해선 반드시 필요한 성질이다. 분명히 $\gcd (n , m) =1$ 라는 조건이 있으니 만능이라고 착각하진 말자.

증명

일반성을 잃지 않고, $$nm = p_{1}^{{k}_{1}} p_{2}^{{k}_{2}} \cdots p_{r}^{{k}_{r}} \\ p_{1} < p_{2} < \cdots < p_{r}$$ 라고 하자. 가정에서 $\gcd (n , m ) = 1$ 이므로 $p_{i} \mid n$ 이거나 $p_{i} \mid m$ 이거나 둘 중 하나여야만한다.

• $p_{i} \mid n$ 을 만족하도록 하는 소수들을 $N_{1} , N_{2}, \cdots , N_{r_{1}}$
• $p_{i} \mid m$ 을 만족하도록 하는 소수들을 $M_{1} , M_{2}, \cdots , M_{r_{2}}$

이라고 하면 $$n = N_{1}^{a_{1}} N_{2}^{a_{2}} \cdots N_{r_{1}}^{a_{r_{1}}} \\ m = M_{1}^{b_{1}} M_{2}^{b_{2}} \cdots M_{r_{2}}^{b_{r_{2}}}$$ 으로 나타낼 수 있고 $$\begin{align*} \phi ( nm ) =& nm \prod_{p \mid nm} \left( 1- {{1} \over {p}} \right) \\ =& p_{1}^{{k}_{1}} p_{2}^{{k}_{2}} \cdots p_{r}^{{k}_{r}} \prod_{p \mid nm} \left( 1- {{1} \over {p}} \right) \\ =& N_{1}^{a_{1}} N_{2}^{a_{2}} \cdots N_{r_{1}}^{a_{r_{1}}} M_{1}^{b_{1}} M_{2}^{b_{2}} \cdots M_{r_{2}}^{b_{r_{2}}} \prod_{p \mid nm} \left( 1- {{1} \over {p}} \right) \end{align*}$$ 다시 한 번, 가정에서 $\gcd (n , m ) = 1$ 이므로 $p \mid n$ 이거나 $p \mid m$ 이거나 둘 중 하나여야만 하므로 $$\begin{align*} \phi ( nm ) =& N_{1}^{a_{1}} N_{2}^{a_{2}} \cdots N_{r_{1}}^{a_{r_{1}}} M_{1}^{b_{1}} M_{2}^{b_{2}} \cdots M_{r_{2}}^{b_{r_{2}}} \prod_{p \mid n} \left( 1- {{1} \over {p}} \right) \prod_{p \mid m} \left( 1- {{1} \over {p}} \right) \\ =& N_{1}^{a_{1}} N_{2}^{a_{2}} \cdots N_{r_{1}}^{a_{r_{1}}} \prod_{p \mid n} \left( 1- {{1} \over {p}} \right) M_{1}^{b_{1}} M_{2}^{b_{2}} \cdots M_{r_{2}}^{b_{r_{2}}} \prod_{p \mid m} \left( 1- {{1} \over {p}} \right) \\ =& \phi ( n ) \phi ( m ) \end{align*}$$

■