11.2.4. Helping Lemma

Try these first

1. 1.

   What does it mean for a number 'a' to divide 'b'?

   Hint

   Think about the division operation.

2. 2.

   State Euclid's Lemma in your own words.

   Hint

   Relate it to an example you’ve seen.

3. 3.

   What does Euclid’s Lemma state?

   • p divides the product implies p divides none of them
   • p divides the product implies p divides at least one of them
   • p is always greater than one

   Hint

   Think about how prime factors interact with products.

4. 4.

   True or False: The Helping Lemma assures the existence of unique solutions in CRT.

   • True
   • False

   Hint

   Remember the implications of congruences and moduli.

5. 5.

   Given the congruences x ≡ 3 mod 4, x ≡ 4 mod 5, and x ≡ 2 mod 6, find all possible values of x.

   Hint

   You must consider each modulus and their pairwise relations.

6. 6.

   Demonstrate why the Chinese Remainder Theorem cannot work if the moduli are not pairwise coprime, with a specific example.

   Hint

   Think about divisibility and overlap in factors.