Annual Harvard-MIT Mathematics Tournament

Solution:
Note that
$$\sigma(m n) \phi(m n) = \sigma(m) \phi(m) \sigma(n) \phi(n) \leq (m^{2}-1)(n^{2}-1) = (m n)^{2} - (m^{2} + n^{2} - 1) < (m n)^{2} - 1$$
for any pair of relatively prime positive integers $(m, n)$ other than $(1,1)$. Now, for $p$ a prime and $k$ a positive integer, $\sigma\left(p^{k}\right) = 1 + p + \cdots + p^{k} = \frac{p^{k+1}-1}{p-1}$ and $\phi\left(p^{k}\right) = p^{k} - \frac{1}{p} \cdot p^{k} = (p-1) p^{k-1}$. Thus,
$$\sigma\left(p^{k}\right) \phi\left(p^{k}\right) = \frac{p^{k+1}-1}{p-1} \cdot (p-1) p^{k-1} = (p^{k+1}-1) p^{k-1} = p^{2k} - p^{k-1} \leq p^{2k} - 1$$
with equality where $k=1$. It follows that equality holds in the given inequality if and only if $n$ is prime.