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)