11.2.1. Properties of Divisibility

Try these first

1. 1.

   What does Bezout's theorem state?

   Hint

   Think about expressing GCD in terms of a linear combination.

2. 2.

   What does Euclid's lemma suggest about prime numbers?

   Hint

   Consider prime factors when multiplying numbers.

3. 3.

   What does Bezout's theorem relate to?

   • Prime Factorization
   • GCD
   • Division

   Hint

   Look for the theorem's key term.

4. 4.

   True or False: Euclid's lemma states a prime must divide all factors in a product.

   • True
   • False

   Hint

   Remember its definition regarding primes.

5. 5.

   Prove the uniqueness of the solution in CRT when given two congruences a ≡ x (mod m) and b ≡ x (mod n) with m and n coprime.

   Hint

   Use the properties we discussed in specifics.

6. 6.

   Using a set of numbers with primes, prove that for any number k, if p divides the product of k numbers, p must divide at least one number.

   Hint

   Break it down with induction steps.