0
$\begingroup$

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

...?

  • 1
    Reading up on it now.2012-07-28

3 Answers 3

1

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$?

  • 0
    Thanks so much! That was really helpful.2012-07-28
4

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.

4

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\ $