State and prove the Principle of Inclusion and Exclusion.

Use the Principle to show that the Euler totient function $\phi$ satisfies

$$\phi\left(p_{1}^{c_{1}} \cdots p_{r}^{c_{r}}\right)=p_{1}^{c_{1}-1}\left(p_{1}-1\right) \cdots p_{r}^{c_{r}-1}\left(p_{r}-1\right) .$$

Deduce that if $a$ and $b$ are coprime integers, then $\phi(a b)=\phi(a) \phi(b)$, and more generally, that if $d$ is any divisor of $n$ then $\phi(d)$ divides $\phi(n)$.

Show that if $\phi(n)$ divides $n$ then $n=2^{c} 3^{d}$ for some non-negative integers $c, d$.