Show $\phi(n)$ = $n \Pi_{p \vert n} (1 - \frac{1}{p})$

Question

(Here $\phi$ is the Euler Totient Function, $p$ all the primes dividing $n$) So I wanted to know is the best way to prove this using induction on $n$? or to suppose cases where $n$ is prime or composite? which would be the best approach? I am lost on how to approach this..

Answer 1

Hint:

Let $p$ be a prime such that $p \not\mid n$, then $$\phi(pn)=(p-1)·\phi(n)$$ Let $p$ be a prime such that $p\mid n$, then $$\phi(pn)=p·\phi(n)$$

Prove and apply these properties to all prime factors of $n$.