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

...?

  • 0
    Do you know about unique prime factorizations?2012-07-28
  • 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
    Yes! working on it..thanks for your help.2012-07-28
  • 0
    I understand the logic, but I'm not sure how to word it correctly according to proof standards.2012-07-28
  • 0
    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.$2012-07-28
  • 0
    @rookie_02 see my comment above.2012-07-28
  • 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\ $