Talk:Euclid's lemma

$a{\frac {b}{p}}=n\ ,$

and since gcd(a, p) = 1 and n is an integer, b/p must also be an integer

I'm afraid you've lost me. How can you draw this conclusion without assuming either Euclid's lemma or uniqueness of prime factorization (the first of which certainly involves circular reasoning and is thus a logical fallacy, and the secdon of which is vulnerable to the same danger since Euclid's lemma is often used for proving uniqueness of factorazation)? Michael Hardy 20:35, 3 August 2007 (CDT)

How do you feel about the following?

Lemma: Suppose p and q are relatively prime integers and that p|kq for some integer k. Then p|k.

Proof: Because p and q are relatively prime, the Euclidean Algorithm tells us that there exist integers r and s such that 1=gcd(p,q)=rp+sq. Next, since p|kq there exists some integer n such that np=kq. Now write

k=(rp+sq)k = rpk + s(kq) = rpk + snp = p(rk+sn).

Since rk+sn is an integer, this shows that p|k as desired.

(Is there an end-of-proof symbol we should use?)

Now in the proof of Euclid's Lemma, since p|ab and a and p are relatively prime, by the above lemma p|b so the proof is complete.

The proof can also be rephrased along these lines:

Let a, b, p $\in \mathbb {Z}$ with p prime, and suppose that p is a divisor of ab, p|ab. Now let g=gcd(a,p). Since p is prime and g divides it, then either g=p or g=1. In the first case, p divides a by the definition of the gcd, so we are done. In the second case we have that a and p are relatively prime and that p|ba so by the above lemma, p divides b. Thus in either case p divides (at least) one of a and b.

Michael Underwood 13:55, 8 August 2007 (CDT)

I haven't yet looked at the proof carefully, but I think this way of stating the lemma makes it appear more complicated that it really is. The version in the article is good. I'll be back later...... Michael Hardy 14:39, 8 August 2007 (CDT)

The lemma I stated above isn't Euclid's Lemma, but can be used to prove it. I agree that the version in the article is good and I'm not trying to change anything you've written, only add the proof to it. This additional lemma is what lets me draw the conclusion that you were initially worried about. Michael Underwood 15:55, 8 August 2007 (CDT)

Well, that's a predictable misunderstanding, so it should be phrased differently. Michael Hardy 14:59, 13 August 2007 (CDT)