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

■