# 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.

• Strong Hint: Squaring $a$ does not add any new prime factors. – Coffee_Table Apr 25 '14 at 15:36
• So you already know (some) properties of gcd and lcm, but you don't yet know the fundamental theorem of arithmetic / uniqueness of prime factorizations? – Bill Dubuque Apr 25 '14 at 15:38
• He has shown us how to use the FTA and did suggest to use it to prove this proof but I haven't fully grasped how to use the FTA in any of my proofs yet. Still sinking in. – Justin Apr 25 '14 at 15:41
• Well, one definition of prime is that $p\mid ab$ implies $p\mid a\lor p\mid b$ ... – Hagen von Eitzen Apr 25 '14 at 15:43

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.

• @BillDubuque I think saying "it implies the prime divisor property" is a bit of a grand way of putting something so simple, especially for a beginning student. – Jack M Apr 25 '14 at 16:09
• But the Prime Divisor Proper is the essence of the matter here, and the sooner one grasps that simple concept the better a commmand one will have over number theory of $\,\Bbb Z\,$ (or any UFD). The PDP is equivalent to uniqueness of prime factorization (this being a special case of the easy direction of that equivalence) – Bill Dubuque Apr 25 '14 at 16:11
• @BillDubuque I included more details at the "handwavy" part. What I think you're forgetting is that, yes formal reasoning with things like the PDP is important, but not before grasping the siutation intuitively. I'm sure you yourself apply intuitive reasoning like the above constantly, even if you then replace it with a formal argument. The OP will not be well served by being trained to do arithmetic solely by the application of rules without ever having been made aware of the "intuitive" content of unique factorization. – Jack M Apr 25 '14 at 16:33
• @Jack That looks better. I agree that one needs the intuitive understanding too, but that needs to be done very carefully here because we have so much empirical intuitive knowledge of integer arithmetic that it is sometimes difficult for beginning students to separate empirical from logical deduction. – Bill Dubuque Apr 25 '14 at 16:36

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.