11.2.2. Euclid’s Lemma

Try these first

1. 1.

   Define what it means for a number p to be prime.

   Hint

   Consider the smallest prime examples.

2. 2.

   What does it mean if p divides a product of numbers?

   Hint

   Think about factors of numbers.

3. 3.

   What does Euclid's Lemma state?

   • A prime divides all products
   • A prime divides at least one factor of a product
   • None of the above

   Hint

   Review the definition of primes.

4. 4.

   True or False: If p divides ab, then p must also divide a.

   • True
   • False

   Hint

   Think about counterexamples.

5. 5.

   Prove by induction that if a prime divides a product of any n integers, it divides at least one of those integers.

   Hint

   Focus on how the prime interacts with the product.

6. 6.

   Using Euclid's Lemma, show why it implies that any solution to a system of linear congruences in CRT must be unique.

   Hint

   Assess the implications of congruences.