# Show $\phi(n)=n\prod_{i=1}^{r}\left(1-\frac{1}{p_i}\right)$

If $m$ and $n$ are two integers such that $\gcd(m,n)=1$, then we have $\phi (mn)=\phi (m) \phi(n)$, where $\phi$ is the Euler phi function defined by $\phi(n)=|\mathbb{Z_n^*}|$. Use the fact to show that if $n$ has the canonical factorization $\prod_{i=1}^{r}p_i^{e_i}$ for distinct primes $p_1,...,p_r$ and $e_i\geq1$, then $$\phi(n)=n\prod_{i=1}^{r}\left(1-\frac{1}{p_i}\right).$$ I have no idea what $\phi(n)=|\mathbb{Z}_n^*|$ is. Can anyone guide me on this question?

-
There is no question. en.wikipedia.org/wiki/Euler%27s_totient_function will help you. –  Martin Brandenburg Jan 29 '13 at 14:47
You need to use that the different prime powers are pairwise relatively prime, and then you need to find $\phi(p^k)$ for a fixed prime power $p^k$. After that some algebra to get the formula. –  coffeemath Jan 29 '13 at 14:49

For a positive integer $n$, $\phi(n)$ is the number of positive integers not exceeding $n$ that are coprime to it. Since the positive integers not exceeding a prime power $p^e$ that are not coprime to it are precisely the multiples of $p$ and there are exactly $p^{e-1}$ such multiples, $\phi(p^e)=p^e-p^{e-1}=(1-\frac{1}{p})p^e$. It follows that
$\phi(p_1^{e_1}...p_r^{e_r})$
$=\phi(p_1^{e_1})...\phi(p_r^{e_r})$
$=(1-\frac{1}{p_1})p_1^{e_1}...(1-\frac{1}{p_r})p_r^{e_r}$
$=n(1-\frac{1}{p_1})...(1-\frac{1}{p_r})$.