📂Number Theory

Proof of the Multiplicative Property of Totient Functions

Theorem ¹

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

Description

It is an essential property to obtain various important results derived from the torsion function. There’s definitely a condition called $\gcd (n , m) =1$, so don’t be mistaken for it being almighty.

Proof

Without loss of generality, $$nm = p_{1}^{{k}_{1}} p_{2}^{{k}_{2}} \cdots p_{r}^{{k}_{r}} \\ p_{1} < p_{2} < \cdots < p_{r}$$ Let’s assume. Since $\gcd (n , m ) = 1$ from the assumption, it must be either $p_{i} \mid n$ or $p_{i} \mid m$.

• Primes satisfying $p_{i} \mid n$ are denoted as $N_{1} , N_{2}, \cdots , N_{r_{1}}$
• Primes satisfying $p_{i} \mid m$ are denoted as $M_{1} , M_{2}, \cdots , M_{r_{2}}$

Then, it can be expressed as $$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}}}$$ and $$\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*}$$ Again, since from the assumption $\gcd (n , m ) = 1$, it must be either $p \mid n$ or $p \mid m$, therefore $$\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*}$$

■