I'm currently working on this problem:

We know that if $m,n \in \mathbb{N}$ are pair wise, relatively prime integers, then $\phi(m,n) = \phi(m) \times \phi(n)$ Prove by induction that if $m_1,...,m_r$ are pair-wise relatively prime positive integers, then $\phi(m_1\cdot m_r) = \phi(m_1)\cdot\cdot\cdot\phi(m_r).$

What I have so far:

For our base case, let $r=2$

Then $\phi(m_1\cdot m_r)=\phi(m_1)\cdot\cdot\cdot\phi(m_r)$ is the same as $\phi(m_1\cdot m_2)=\phi(m_1)\phi(m_2)$ which is the given property, so we know that the base case holds.

The inductive step is what I'm not sure about. Any pointers regarding how I could proceed?


We know that $\varphi(n)=\left|\mathbb{Z}/(n\mathbb{Z})^*\right|$.
Assuming that $m,n$ are coprime, by the Chinese remainder theorem we have $$ \mathbb{Z}/(mn\mathbb{Z})^*\simeq \mathbb{Z}/(m\mathbb{Z})^*\times \mathbb{Z}/(n\mathbb{Z})^*$$ hence $\varphi(mn)=\varphi(m)\cdot\varphi(n)$, and if $m_1,\ldots,m_r$ are pairwise coprime, $$\varphi\left(\prod_{k=1}^{r}m_k\right)=\prod_{k=1}^{r}\varphi(m_k).$$

Alternative way: we may use the inclusion-exclusion principle to show that in general $$\varphi(n) = n\cdot\prod_{p\mid n}\left(1-\frac{1}{p}\right) $$ hence the multiplicativity of $\varphi$ follows from the fact that coprime integers have disjoint sets of prime divisors.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.