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.

  • 1
    $\begingroup$ 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$. $\endgroup$ – DanielWainfleet Jan 5 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$.

  • $\begingroup$ Woah, thanks! I'm just a beginner, so this helps me a lot. $\endgroup$ – Data Space Jan 4 at 18:40
  • $\begingroup$ @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$. $\endgroup$ – Bill Dubuque Jan 4 at 19:06
  • $\begingroup$ @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 $\endgroup$ – Data Space Jan 4 at 22:36
  • $\begingroup$ @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. $\endgroup$ – Data Space Jan 4 at 23:05
  • $\begingroup$ @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. $\endgroup$ – Bill Dubuque Jan 5 at 0:02

Here is a different approach. Unique prime factorization of $n,$ for $1<n\in \Bbb N,$ 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.$

  • $\begingroup$ 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$. $\endgroup$ – DanielWainfleet Jan 5 at 2:55
  • $\begingroup$ <3 I really liked this proof, thanks for such logical piece. $\endgroup$ – Data Space Jan 5 at 2:57
  • 2
    $\begingroup$ @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) $\endgroup$ – Bill Dubuque Jan 5 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.