Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

Of course we are familiar with the notion that if $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$ ($p_{i}$ distinct primes; $k_{i}>0$), then $$\varphi\left(n\right)=n\left(1-1/p_{1}\right)\left(1-1/p_{2}\right)\cdots\left(1-1/p_{r}\right),$$ where $\varphi$ is the Euler totient function.

The goal is to prove this using the fact that $\varphi$ is multiplicative, that is, $$\varphi\left(mn\right)=\varphi\left(m\right)\varphi\left(n\right),$$ given that $m$ and $n$ are coprime.

Proving the former notion from the multiplicative property. But how do we prove the multiplicative property of $\varphi$ without using that notion?

share|cite|improve this question

marked as duplicate by Martin Brandenburg, Davide Giraudo, Shuhao Cao, Andrey Rekalo, Vedran Šego Sep 6 '13 at 19:17

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

What is the definition of $\varphi$ you are using? – Zev Chonoles Sep 6 '13 at 4:50
Note that $\phi(mn)=\phi(m)\phi(n)$ if and only if $m$ and $n$ are coprime. For example, $\phi(2)=1$, but $\phi(2\cdot2)=\phi(4)=2\ne1\cdot1=1$. That might make things easier. – William Ballinger Sep 6 '13 at 4:51
@AnthonyCarapetis, the goal this time is to prove it the other way around. So I need to prove the multiplicative property first. – vantonio1992 Sep 6 '13 at 5:05
@vantonio1992: oh sorry, I clearly skimmed too fast. – Anthony Carapetis Sep 6 '13 at 5:08

Let us start from the definition of Euler's Phi: $$ \varphi(n)=|\{x\in [1,n-1] | \gcd(x,n)=1\}|, $$ i.e., $\varphi(n)$ is the number of positive integers at most equal to $n$ and prime to $n$.

Now, if $n$ and $m$ are coprime, we want to show that $\varphi(mn)=\varphi(n)\varphi(m)$. For this, let us denote: $$ \Phi(n)=\{x\in [1,n-1] | \gcd(x,n)=1\}. $$ We just want to show that $\Phi(mn)$ has the same cardinality as $\Phi(m)\times\Phi(n)$. To do this, we can use the Chinese Remainder Theorem (since $m$ and $n$ are coprime) to construct a bijection between the two sets. This bijection is given by $x \rightarrow (x\bmod{m},x\bmod{n})$.

The only thing you need to check is that $x$ is prime to $mn$, if and only if, $x \mod {m}$ is prime to $m$ and $x \mod {n}$ is prime to $n$.

share|cite|improve this answer

The group $(\mathbb{Z}/n\mathbb{Z})^*$ has order $\phi(n)$. Because $(\mathbb{Z}/nm\mathbb{Z})^*\simeq (\mathbb{Z}/n\mathbb{Z})^*\times (\mathbb{Z}/m\mathbb{Z})^*$ for coprime $n$ and $m$ it follows $\phi(nm)=\phi(n)\phi(m)$.

share|cite|improve this answer

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