CBSE Class 10 Answered

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.