10.4. Statement of the Chinese Remainder Theorem

So, let us see how we can solve linear congruences using extended Euclid’s algorithm that is our method number one.

Linear congruences are equations of the form ax ≡ b (mod N), where a, b, and N are integers. In this equation, we want to find the unknown variable x, which satisfies the given relationship under modulo N. Unlike regular linear equations where you can simply divide by a (assuming a is not zero), in modular arithmetic, we refer to the multiplicative inverse of a to solve for x.

Think of linear congruences like sharing candies among friends in a circle. Suppose you have a fixed number of candies (let's say 10), and you want to distribute them evenly. If there are 3 friends, when you give each friend some candies, you notice some candies remain unshared. If you were to calculate how many candies each friend had (twice that amount), it would be like finding multiple solutions in linear congruences.

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.

The Chinese Remainder Theorem (CRT) provides a way to find an unknown number x that meets multiple linear congruences. For instance, if we know the remainders of x when divided by different moduli (like 3, 5, and 7), CRT guarantees that there is at least one solution x that satisfies all these conditions, given the moduli are pairwise coprime.

Imagine you are trying to find a time when multiple clocks show specific times. One clock shows 2 o'clock for every 3 hours, another clock shows 3 o'clock every 5 hours, and a third shows 2 o'clock every 7 hours. The CRT helps us find a common time when all clocks align, ensuring you get to all your appointments on time!

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 and m they are co-prime to each other.

The formal statement of the Chinese Remainder Theorem is as follows: given n pairwise coprime moduli, and corresponding remainders, there exists a unique solution modulo the product of the moduli. This means if you can find one solution x that meets all the linear congruences, all other solutions can be derived from it by adding multiples of the product of the moduli.

Think about a password that fits multiple criteria: it must have specific characters at certain positions (like a mix of letters, numbers, and symbols). CRT is like a master key that helps you find one password that fits all the criteria at once, ensuring you can access your account efficiently without confusion.

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.

To find a solution using CRT, we express the unknown x as a linear combination of the provided remainders. We will construct special linear combiners that satisfy certain properties: each combiner will yield 1 when reduced modulo its corresponding modulus and 0 when reduced modulo others. This ensures that we are creating a solution that respects all given congruences.

Think of making a smoothie where each fruit represents a remainder. To get a perfect taste (unique solution), you need just the right amount of each fruit while ensuring none overpowers the others. The special linear combiners are like the perfect ratios of fruits you need to balance out the flavors in your smoothie!

--