Proof of Euclid's Lemma
Asked by | 31st May, 2009, 12:30: PM
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
Kindly Sign up for a personalised experience
- Ask Study Doubts
- Sample Papers
- Past Year Papers
- Textbook Solutions
Verify mobile number
Enter the OTP sent to your number