11.1. Discrete Mathematics

Hello everyone, welcome to this lecture, so, in this lecture we will continue our discussion regarding solving linear congruences using CRT. And specifically we will focus on the uniqueness part of the solution. So, we want to prove that there exists a unique solution in the range 0 to M - 1 satisfying the system of linear congruence.

This chunk introduces the topic of uniqueness in the context of the Chinese Remainder Theorem (CRT). The CRT helps in solving systems of linear congruences, which are equations that express relationships between integers with respect to a divisor (or modulus). In particular, this portion emphasizes the goal of the lecture: to establish that each solution lies within a unique range, specifically from 0 to M - 1. Here, 'M' represents the product of the moduli involved in the system of congruences.

Imagine you have a special combination lock that can only be set to numbers 0 through M-1, where M is a predefined maximum number. Each valid combination corresponds to a valid sequence of moves, and the goal is to find one unique sequence that gets you to the correct combination. Just like in the CRT, where only one unique solution within a set range can be found.

So, we start with some basic properties of divisibility, so the first property is the following imagine you are given 3 positive integers a, b, c and it is given to you that a divides the product of b and c but a is co-prime to b. Then I can conclude that a divides c.

This chunk discusses a fundamental property of divisibility. It states that if we have three positive integers (a, b, c) such that 'a' divides the product of 'b' and 'c' (indicated by the mathematical notation a | (b * c)), and that 'a' is co-prime to 'b' (meaning they have no common factors other than 1), then it follows that 'a' must also divide 'c'. This property is useful in proofs involving congruences, particularly in establishing relationships between different numbers based on their divisibility.

Think of 'a' as a key that can open a specific lock (the product of 'b' and 'c'). If 'b' is not related to the key at all (since they're co-prime), then for the key to fit, it must belong to 'c'. This shows that knowing a key opens certain combinations can lead to understanding more about which individual locks can also be opened.

Now we prove another property which we often call as the Euclid’s Lemma, which is also very useful while proving the uniqueness part of the CRT theorem. So, the Euclid’s Lemma, is as follows, it says that if p is a prime number and if it is given that p divides the product of n numbers. Then definitely, it has to be the case that p divides at least one of those n numbers.

Euclid's Lemma is a significant property in number theory that states if a prime number 'p' divides a product of several numbers, it must also divide at least one of those individual numbers from the product. This lemma is crucial in proofs and theorems within number theory, particularly for establishing the properties of primes and their role in divisibility. It will specifically help in proving statements related to the uniqueness of solutions of the congruences in CRT.

Consider a situation where p is a key that can open multiple doors (the product of n numbers). If the key can open a set of combined doors, then logically, it must be able to open at least one door in the mix. This analogy illustrates how primes function similarly - if a prime divides something combined, it must also divide an individual part of that combination.

So, again we will take the help of a helping lemma and this helping lemma will be useful later as well. So, what this helping lemma says is the following: imagine you are given n modulus which are pairwise relatively prime that means, you take any pair of modulus m and m they are co-prime to each other. And suppose you know that you are given 2 numbers a and b which are congruent with respect to all the n individual modulus.

This chunk introduces a helper lemma critical for proving the uniqueness of the solution in the CRT. It is stated that when you have 'n' moduli that are all pairwise relatively prime, if two numbers, 'a' and 'b', are congruent under each of these moduli, then they must also be congruent under the product modulus 'M', which is the product of these individual moduli. This concept serves as the foundation for further demonstrating that if two different solutions exist, they must coincide in the range of interest.

Imagine a library with different sections (the moduli) for various genres. If two books (a and b) have the same themes across all genres, it suggests they likely fall under a single overarching storyline that can be directly associated with the library's overall categorization (the modulus M).

So, we have proved the helping lemma now, coming back to the proof of the uniqueness of the solution, we wanted to prove that there is a unique solution x in the range 0 to M - 1 satisfying the system of n linear congruences... and since both x and y were in the range 0 to M - 1, that means they were strictly less than M, and both of them are congruent, then that is possible only when x = y that shows that there exists a unique solution modulo M satisfying your system of linear congruence.

In this final chunk, the lecture wraps up its discussion by returning to the unified proof that demonstrates why there can only be one unique solution in the specified range for the set of linear congruences. Starting with the assumption that there are two solutions, the logical argumentation leads to the conclusion that these two solutions must actually be equal. This shows conclusively that the CRT guarantees a unique solution, reinforcing its importance in solving congruences.

Think of a puzzle where several pieces can only fit together in one specific way to complete a picture. If two people claim to have completed the puzzle but they do it in the same space designed for one configuration, it logically follows they ended up with the same arrangement, emphasizing the uniqueness of successful solutions.

So, say we want to find out this unknown x satisfying the system of linear congruences: x ≡ 2mod3, x ≡ 3mod5, x ≡ 2mod7. So, we will find out the bigger modulus and sum modulus so, the bigger modulus will be the product of 3, 5, 7 and you can see your m is 3, m is 5, m is 7 and a is 2, a is 3 and a is 2. So, my bigger modulus will be 105.

This chunk illustrates an application of the Chinese Remainder Theorem through a specific example involving three congruences. By calculating the product of the moduli (3, 5, and 7), the total modulus M is found to be 105. The method then continues by calculating needed elements to derive a unique solution through multiplication of found inverses and substituting back to find 'x'. This step-by-step application solidifies the lecture's earlier theoretical discussion.

Consider a restaurant where customers can make three different meal choices, and each meal has a different time window when it's available. If each customer must choose one meal and must decide within those time frames, figuring out the common time frame (M) to ensure everyone can enjoy their meals is akin to finding the value of x in this theorem.

--