How to prove if $n$ is prime and $n | a^2$ then $n | a$? My professor assigned this for homework but I don't understand how to connect the dots. He suggested using the fact that $\gcd (x,y) \cdot \operatorname{lcm} (x,y) = xy$ but I'm not sure how that's relevant.

The other answers sure are technical for such a conceptually simple question.
$a$ can be factored uniquely into primes:
$$a=p_1...p_n$$
So $a^2$ looks like this:
$$a^2=p_1...p_np_1...p_n$$
Because prime factorization is unique, if $n$ divides $a^2$, that means $n$ is one of the $p_i$. In more detail, if $n$ divides $a^2$, then we can write $a^2=nx$ for some $x$. Factoring $x$ into primes, we get a new factorisation for $a^2$ including the prime $n$, and since this factorization must be the same as the original one (up to rearranging the factors), $n$ must be one of the $p_i$. So therefore it divides $a$.
The point is just that squaring doesn't introduce any new primes into the factorization, so if a prime is in there after squaring, it had to be in there before squaring too.
