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.

prime $p|ab$, then $p|a$ or $p|b$.

so, if $a=b$, $p|a^2$, we must have $p|a$

If $p\nmid a$, then $(p,a)=1$. Bézout's identity

$$px+ay=1$$

so

$$pxb+aby=b$$

we get $p|b$

Said gcd, lcm law does imply the Prime Divisor Property (PDP): $ $ prime $\,p\mid ab,\ p\nmid a\,\Rightarrow\,p\mid b$

Hint $\ $ By said law, $\,\gcd(a,p)=1\,\Rightarrow\,\color{#c00}{{\rm lcm}(a,p)=ap},\,$ so $\,a,p\mid ab\,\Rightarrow\,\color{#c00}{ap}\mid ab\,$ so $\,\ldots$

Remark $\ $ If existence and uniqueness of prime factorizations is already known then the PDP follows easily: $ $ if $\,p\mid ab\,$ then $\,pc = ab.\,$ Appending $\,p\,$ to the prime factorization of $\,c\,$ yields one prime factorization of $\ pc = ab.\,$ Appending the prime factorizations of $\,a,b\,$ yields another. By uniqueness, they have equal sets of primes, $ $ i.e. with $\,\cal P(k) =$ set of prime factors of $\,k,\,$ we have that $\,\{p\}\cup\cal P(c) = \cal P(a)\cup \cal P(b),\,$ so $\,p\in\cal P(a)\,$ or $\,p\in\cal P(b),\,$ so $\,p\mid a\,$ or $\,p\mid b\ \ $ QED

Yours is the special case $\ b = a\ $ in PDP, $ $ i.e. prime $\ p\mid a^2\Rightarrow\, p\mid a.\ $ An obvious indcution extends the proof to a product of any number of factors, i.e. prime $\,p\mid a_1\cdots a_n\,\Rightarrow\, p\mid a_i\,$ for some $\,i.\,$ Said in words: $ $ if a prime divides a product then it divides some factor of the product.