10.3. Chinese Remainder Theorem (CRT)

Instead I will discuss another way of solving linear congruences; in fact, a set of linear congruences and this method is often called as the Chinese Remainder Theorem attributed to the ancient Chinese but it is also believed that the ancient Indian mathematicians also used the same technique for solving a system of linear congruences. So, what exactly we mean by system of linear congruences.

The Chinese Remainder Theorem (CRT) is a method for solving systems of linear congruences. It is an important theorem in number theory that allows us to find a unique solution to a system of equations modulo different integers, given those integers are coprime. This means the theorem can be applied in scenarios where we have multiple modular equations, each with its set of remainders.

Imagine scheduling events where you have to find a common time that works for everyone. For instance, if person A is free on weekdays and needs to schedule meetings so they can always have a free slot, while person B is free on weekends but needs to pick a time that fits both. The CRT helps find a solution (a time/date) that works for both parties under their unique availability constraints, represented as modular equations.

So, let me now formally state the theorem statement of Chinese remainder theorem and then we will prove it. So, you are given n different modulus which are pairwise relatively prime, that means, you take any pair of modulus m_i and m_j they are co-prime to each other. And you are given n number of remainders a_1 to a_n. So, you have to find out an unknown x which is congruent to a_1 modulo m_1, it is congruent to a_2 modulo m_2 and so on up to a_n modulo m_n.

The theorem asserts that if you have several remainders from multiple equations, and if the moduli are coprime, then there exists a unique solution x modulo the product of these moduli. The uniqueness means that within the range defined by the product, there is exactly one solution that satisfies all equations simultaneously.

Think of a clock that shows different times based on different time zones. If you want to set an appointment considering multiple time zones (e.g., New York, London, Tokyo), CRT helps adjust those times to find a single time that fits everyone, ensuring that it's a unique and valid time when viewed from the perspective of all participating locations.

So, now we want to prove the Chinese Remainder theorem and there are multiple things which we have to prove, the proof strategy is as follows, we will give the construction of one of the solutions in the range 0 to M - 1. But that does not mean that is a unique solution, remember there are 2 parts of the proof, we have to show that there is at least one solution in the range 0 to M - 1 which we will be doing in this lecture.

To find a solution, one constructs a special linear combination of the given remainders, using their respective moduli. It involves creating separate terms for each modulus where the contributions from non-target moduli sum to zero, ensuring the overall equation conforms to the conditions prescribed by CRT. This method ensures the derived solution reflects the required remainders when checked against each modulus.

Picture a recipe that requires certain quantities of ingredients, where each ingredient can be sourced from different shops. You need to determine how much of each ingredient to buy, ensuring the total amounts meet specific needs (the remainders); this mirrors solving the CRT where each ingredient's quantity corresponds to a congruence condition.

So now, let us see how exactly we can find at least one solution that will be the goal of this lecture. So, the construction idea of that solution will be as follows: we will define; we will try to find out a special linear combination of the n remainders that are given to us.

The process involves defining a comprehensive product of the moduli, M, excluding one modulus at a time. For each modulus, we find a multiplicative inverse that helps ensure the combined conditions of all equations hold true. By constructing a unique combination of these inverses with the remainders, we can derive the solution x that meets the desired conditions laid out by the theorem.

Consider an artist mixing colors to create a specific shade. Each color represents one of the modulus, and through careful balancing and combining—much like using multiplicative inverses—the artist achieves the precise hue that meets their artistic vision, analogous to finding a solution that satisfies the CRT.

--