MODBasic Intermediate

Problem - 4195

Show that two positive integers $m$ and $n$ are co-prime if and only if $\varphi(mn)=\varphi(m)\varphi(n)$.


Let $p_i$ be the common prime divisors of $m$ and $n$, if any. Let $q_i$ be those prime factors which divide $m$, but not $n$. Let $r_i$ be those prime factors which divide $n$, but $m$. Then we have $$m=\prod p_i^{\alpha_i}\prod q_j^{\beta_j}$$

and $$n=\prod p_i^{\gamma_i}\prod r_j^{\delta_j}$$

where $\alpha_i$, $\beta_i$, $\gamma_i$ and $\delta_i$ are all non-negative integers. Then we have $$\varphi(mn)=mn\prod \left(1-\frac{1}{p_i}\right)\prod \left(1-\frac{1}{q_j}\right)\prod \left(1-\frac{1}{r_k}\right)$$

and $$\varphi(m)\varphi(n)=mn\prod \left(1-\frac{1}{p_i}\right)^2\prod \left(1-\frac{1}{q_j}\right)\prod \left(1-\frac{1}{r_k}\right)$$

Now, it is clear that these two will equal if and only if the term $\prod \left(1-\frac{1}{p_i}\right)$ vanishes which means that $m$ and $n$ do not share any common prime divisors, i.e. they are co-prime.

report an error