Exercise · ZW-EUCLID-S-LEMMA-010 · ★★★ Advanced
If \(p\) is prime, \(p \mid ab\), and \(p \mid a+b\), what follows?
Choose one option.
Show answer
- D. \(p \mid a\) and \(p \mid b\)
Explanation
By the lemma, \(p\) divides \(a\) or \(b\); say \(p \mid a\). Then from \(p \mid a+b\) it follows that \(p \mid b\). Thus both are divisible by \(p\).
Review the concept: Euclid's lemma
If a prime \(p\) divides the product \(ab\), then \(p\) divides \(a\) or \(b\). It is the key property that distinguishes primes from composite numbers.
\[p \mid ab \Rightarrow p \mid a \ \lor\ p \mid b\]
More practice problems: euclid's lemma
- ZW-EUCLID-S-LEMMA-001 If p is prime and p | ab, what can you conclude?
- ZW-EUCLID-S-LEMMA-002 Does Euclid's lemma require p to be prime?
- ZW-EUCLID-S-LEMMA-003 Which is the correct statement of Euclid's lemma?
- ZW-EUCLID-S-LEMMA-004 If p is prime and p | 35, which value can p take?
- ZW-EUCLID-S-LEMMA-005 Which statement about a prime p that does not divide a is true?
- ZW-EUCLID-S-LEMMA-006 If 7 | 12x, what can you conclude about x?
- ZW-EUCLID-S-LEMMA-007 If 11 | ab and 11 nmid a, what happens to b?
- ZW-EUCLID-S-LEMMA-008 If p is prime and p | a^2, what follows?