Let & denote the phi function
Show that if m and n are not relatively prime, then &(m)&(n) < &(mn)
Well, if $\displaystyle (m,n)>1$ then they must have a common prime divisor $\displaystyle p$.
Let $\displaystyle p^{\alpha}$ and $\displaystyle p^{\beta}$ be the greatest powers of p dividng $\displaystyle m$ and $\displaystyle n$ respectively, then $\displaystyle p^{\alpha+\beta}$ is the greatest power of p dividng $\displaystyle m\cdot n$.
But then $\displaystyle \phi\left(p^{\alpha}\right)\cdot \phi\left(p^{\beta}\right) < \phi\left(p^{\alpha+\beta}\right)$ and you can finish it off by remembering $\displaystyle \phi$ is multiplicative.