Step 1: Prove it's true for any power of a prime Step 2: Let $p$ be a prime divisors of n, then from induction, we know that it's true for $\frac{n}{p^{v_p(n)}}$, which is not a perfect square. For any pairs, we induct with $p^0,p^1,p^2,...,p^{v_p(n)}$ Q.E.D