# If a prime $p$ divides $n^2$ then it also divides $n$ - Is this proof correct?

I'm learning Real Analysis by myself and I wanted to prove that if a prime $$p$$ divides $$n^2$$ where $$n$$ is an integer, then $$p$$ divides $$n$$ itself. I saw that proving this is the same as saying that the prime factors of $$n^2$$ are "the same" than those of $$n$$.

In this case, assume there exists a prime factor $$a_q$$ in $$n^2$$ which is not in $$n$$ (proof by contradiction). By Fundamental Theorem of Arithmetic, we can represent $$n^2$$ as $$n^2= a_1 * a_2 * ... * a_x * a_q$$, where every $$a$$ is prime and $$n=k_1 * k_2 * ... * k_y$$ (every $$k$$ is also prime). We know that $$\frac{n^2}{n}=n$$. So (by susbstituting):

$$\frac{n^2}{n}= \frac{a_1*...*a_x*a_q}{k_1*...*k_y}=n \rightarrow \frac{a_1*...*a_x}{k_1*...*k_y}=\frac{n}{a_q}$$

Because $$\frac{n}{a_q}$$ it's not an integer (initial statement), there's at least one $$a_s$$ in the left side of the equation that is not divisible by any $$k$$. Now we have two factors of $$n^2$$ that don't divide $$n$$. We can repeat this process,

$$\frac{a_1*...*a_x*a_s}{k_1*...*k_y}=\frac{n}{a_q} \rightarrow \frac{a_1*...*a_x}{k_1*...*k_y}=\frac{n}{a_q*a_s}$$,

for each prime factor of $$n^2$$ which means that there's no factor $$a_i$$ in $$n^2$$ divisible by any factor $$k_j$$ of $$n$$. But we knew that $$\frac{n^2}{n}=n$$, hence we have a contradiction ($$n^2$$ is not divisible by $$n$$). So there's no prime factor $$p$$ in $$n^2$$ that does not divide $$n$$ itself $$\rightarrow$$ every prime factor $$p$$ in $$n^2$$ also divides $$n$$.

I'm obviously not an expert in demonstrations so I want to know if this is a valid argument. I'm also aware of Euclid's Lemma, but for this case, ignore it.

• As in the answer from Alex R., an important part of the Fundamental Theorem of Arithmetic is that for $1<n\in \Bbb Z^+,$ the finite sequence $p_1,...,p_m$ such that $n=\prod_{j=1}^mp_j$ is $unique,$ up to a re-arrangement of the order of the terms $p_1,...,p_m$. – DanielWainfleet Jan 5 '19 at 1:59

A shorter way would be to write $$n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$$ (where each $$\alpha_i>0$$) by the Fundamental Theorem of Arithmetic. Then $$n^2= p_1^{2\alpha_1}\cdots p_k^{2\alpha_k}$$. The only primes that divide $$n^2$$ are $$p_1,\cdots,p_k$$ and these clearly also divide $$n$$.

• Woah, thanks! I'm just a beginner, so this helps me a lot. – Data Space Jan 4 '19 at 18:40
• @DataSpace Unfortunately this answer is wrong - your proof is not correct. The claim in the first sentence of the 3rd paragraph is not true, e.g. $p/p^2$ is not an integer, but but there is no prime in the numerator that is not divisible by $p$. – Bill Dubuque Jan 4 '19 at 19:06
• @BillDubuque If $\frac{p}{p^2} = \frac{n}{a_q}$ then $a_q = n*p$ (simple algebra), this contradicts the idea that every $a$ is prime. So your counterexample is not valid.Sorry for the delay :s – Data Space Jan 4 '19 at 22:36
• @BillDubuque Nevertheless, it is true that this proof is not clear at all and contains argumentative"holes". It is, of course, a better idea to just take Alex's proof. – Data Space Jan 4 '19 at 23:05
• @DataSpace But I didn't claim it equals $n/a_q$. The point is that your argument doesn't handle such multiple factors that may occur in the (reducible) fraction. – Bill Dubuque Jan 5 '19 at 0:02

Here is a different approach. Unique prime factorization of $$n,$$ for $$1 follows from the Lemma that if $$a,b,c\in \Bbb Z$$ and $$\frac {ab}{c}\in \Bbb Z$$ while $$\gcd (a,c)=1$$ then $$\frac {b}{c}\in \Bbb Z.$$ The Lemma follows from something called Bezout's Identity, although it is implicit in Euclid's algorithm for computing a $$\gcd$$ : For any $$a,b\in \Bbb Z$$ (not both $$0$$) there exist $$x,y \in \Bbb Z$$ such that $$ax+by=\gcd (a,b).$$

Let $$p$$ be prime and let $$n\in \Bbb Z$$ such that $$p|n^2.$$ Let $$m=\gcd (p,n).$$ Since $$m$$ divides the prime $$p$$ and $$m\ge 1,$$ we have $$m=1$$ or $$m=p.$$

Now there exist $$x,y\in \Bbb Z$$ such that $$px+ny=m,$$ so $$\frac {(m-px)^2}{p}=\frac {n^2y^2}{p}=\frac {n^2}{p}\cdot y^2\in \Bbb Z.$$ But if $$m=1$$ then $$\frac {(m-px)^2}{p}=\frac {1-2px+p^2x^2}{p}=\frac {1}{p}-2x+px^2\in \Bbb Z,$$ implying $$\frac {1}{p}\in \Bbb Z,$$ which is absurd.

So, since we can't have $$m=1,$$ we have $$m=p$$. And since $$m=\gcd (p,n)|n,$$ we have therefore $$p|n.$$

• As matter of style, we could also say that $p|n^2\implies$ $p|n^2y^2=$ $(m-px)^2=$ $=m^2+p(-2mx+px^2)\implies$ $p|m^2,$ to show that $m\ne 1$. – DanielWainfleet Jan 5 '19 at 2:55
• <3 I really liked this proof, thanks for such logical piece. – Data Space Jan 5 '19 at 2:57
• @DataSpace If you're going to permit Bezout then it's easy: $$\,p\mid nn,\ p\nmid n\,\Rightarrow\, kn\!+\!jp = 1\,\Rightarrow\, p\mid knn\!+\!jpn = (kn\!+\!jp)n = n\qquad\qquad$$ Or, equivalently said in terms of gcds $\ \ p\mid nn,pn\,\Rightarrow\, p\mid (nn,pn)=(n,p)n = n.\$ This is essentially a special-case of the Bezout-based proof of EL = Euclid's Lemma (see here for various proofs of EL) – Bill Dubuque Jan 5 '19 at 3:39