# If $p$ is a factor of $m^2$ then $p$ is a factor of $m$

I'm a complete beginner and not sure where to go with this proof of Euclid's lemma. Any help would be greatly appreciated.

If $m$ is a positive integer and a prime number $p$ is a factor of $m^2,$ then $p$ is a factor of $m.$

So far I have:

Since we know that $m$ is a positive integer, then $m^2$ must also be positive. We also know that $p$ is positive integer, since it is a prime number.

So $m^2 = p*k$ where $k$ is positive since both $m^2$ and $p$ are positive. Therefore, $k$ is greater than or equal to $1.$

...?

-
Do you know about unique prime factorizations? –  Andrew Jul 28 '12 at 1:55
Reading up on it now. –  rookie_02 Jul 28 '12 at 2:48

If you know about prime factorization.. the fundamental theorem of arithmetic states that every non-zero integer has a unique (up to ordering) factorization into products of prime powers. That is, $$m = \pm p_1^{k_1} p_2^{k_2} \cdots p_n^{k_n}$$ where $p_i$'s are primes and $k_i > 0$ for all $i.$ ($\pm$ based on the sign of $m.$)

Now what is the prime factorization of $m^2$? It's $$m = p_1^{2k_1} p_2^{2k_2} \cdots p_n^{2k_n}.$$

Can you now use this information to show that $p \ | \ m^2 \implies p \ | \ m$?

-
Yes! working on it..thanks for your help. –  rookie_02 Jul 28 '12 at 2:55
I understand the logic, but I'm not sure how to word it correctly according to proof standards. –  rookie_02 Jul 28 '12 at 7:31
If $p | m^2$ then $p | \prod_i p_i^{k_i}.$ By Euclid's lemma, $p | p_i^{k_i}$ for some $i.$ But both $p, p_i$ are prime, and the only divisors of $p_i^{k_i}$ are $1, p_i, p_i^{k_j}$ for $1 < j < k_i.$ Hence $p = p_i$ for some $i.$ So now we can write $m$ as $m = p_i \prod_{j, j\neq i} p_j^{k_j} = pr,$ for some integer $r.$ I.e. $p | m.$ –  user2468 Jul 28 '12 at 15:51
@rookie_02 see my comment above. –  user2468 Jul 28 '12 at 16:56
Thanks so much! That was really helpful. –  rookie_02 Jul 28 '12 at 21:46

If $p$ is not a prime factor of $m$ then $gcd(p,m)=1$ since $p$ is prime. So there exists integers $x$ and $y$ such that $$xp + ym = 1$$ So $$xmp = m - ym^2.$$ Since $p \mid m^2$, this implies $p \mid m$. Contradiction.

-

Hint $\$ By Euclid's Lemma, $\rm\:p\:|\:m\,k\:\Rightarrow\: p\:|\:m\ \ or\ \ p\:|\:k.\:$ Put $\rm\:k = m.$

Euclid's Lemma $\rm\ \ a\ |\ bc\$ and $\rm\ gcd(a,b)=1\ \Rightarrow\ \color{#C00}{a\ |\ c}\quad$

Proof $\rm\ \ a\ |\ ac,bc\ \Rightarrow\ \color{#C00}a\ |\ gcd(ac,bc) = gcd(a,b)\:c = \color{#C00}c\$

-