Proof of Euclid's Lemma

Asked by  | 31st May, 2009, 12:30: PM

Expert Answer:

The standard proof of Euclid's lemma uses Bézout's identity. This states that, for any relatively prime integers x and y, there exist integers r and s such that

To prove Euclid's lemma, suppose that p is a prime factor of ab, but that p is not a factor of a. Then p and a must be relatively prime, so there exist integers r and s such that

Multiplying through by b gives

Now, the first term on the left is clearly a multiple of p. Since p divides ab, the second term on the left is also a multiple of p. It follows that b is a multiple of p, so p divides b. This proves that p is always either a divisor of a or a divisor of b. Q.E.D.

Virtually the same proof can be used to establish the more general form of Euclid's lemma, with p replaced by the integer n.

Answered by  | 1st Jun, 2009, 02:14: AM

Queries asked on Sunday & after 7pm from Monday to Saturday will be answered after 12pm the next working day.