NumberTheoryBasic Basic

Problem - 2509
Show that if $a$ and $b$ are relatively prime, then $\varphi(a)\varphi(b)=\varphi(ab)$ where $\varphi(n)$ is Euler's totient function.

Let prime factorization of $a$ and $b$ be $a=\displaystyle\prod_{i=1}^{m}p^{\alpha_i}$ and $b=\displaystyle\prod_{i=1}^{n}q^{\beta_i}$. Then $$\varphi(a)\varphi(b)=a\prod_{i=1}^{m}\left(1-\frac{1}{p_i}\right)\cdot b\prod_{i=1}^{n}\left(1-\frac{1}{q_i}\right)=ab\prod_{i=1}^{m}\left(1-\frac{1}{p_i}\right)\prod_{i=1}^{n}\left(1-\frac{1}{q_i}\right)$$

Meanwhile, because $a$ and $b$ are co-prime, we have $$ab=\prod_{i=1}^{m}p^{\alpha_i}\prod_{i=1}^{n}p^{\beta_i}\implies \varphi(ab)=ab\prod_{i=1}^{m}\left(1-\frac{1}{p_i}\right)\prod_{i=1}^{n}\left(1-\frac{1}{q_i}\right)$$

Therefore, the relation holds.

report an error