11.1. Discrete Mathematics

Try these first

1. 1.

   Define a linear congruence. Give an example.

   Hint

   Remember the format of the equation.

2. 2.

   What does it mean for two integers to be co-prime?

   Hint

   Think about their divisibility.

3. 3.

   What does the Chinese Remainder Theorem guarantee?

   • No solutions
   • Unique solution modulo the product of moduli
   • Multiple solutions within bounds

   Hint

   Think about how CRT resolves multiple equations.

4. 4.

   True or False: If two integers are co-prime, they have a common divisor greater than 1.

   • True
   • False

   Hint

   Consider the definition;

5. 5.

   Prove that if a system of n linear congruences has a solution, there is a unique solution modulo the product of the moduli.

   Hint

   Incorporate proof techniques like induction and explore implications of congruences.

6. 6.

   Given the numbers 10, 12, and 15 with a known sum, find numbers congruent to each, ensuring the CRT principles are satisfied.

   Hint

   Break down the system and consider pairwise co-primality.