11.2.5. Example of Chinese Remainder Theorem

So now, let us see an example for Chinese remainder theorem. So, say we want to find out this unknown x satisfying the system of linear congruences: x ≡ 2 mod 3, x ≡ 3 mod 5, x ≡ 2 mod 7.

In this example, we have a set of three linear congruences that we need to solve. Each congruence gives us a remainder when the unknown x is divided by a specific modulus. The goal is to find a single integer x that satisfies all three conditions simultaneously.

Imagine you have a locker system where each locker can only be opened with a specific combination (remainder) when divided by various numbers (moduli). In this case, we want to find a locker number (x) that fits all three combinations.

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.

To find the solution using the Chinese Remainder Theorem, we first calculate the product of all the moduli: M = 3 * 5 * 7 = 105. This larger modulus allows us to work within a single modular framework that encompasses all three original congruences.

Think of M (105) as the total number of lockers after combining them all. Instead of looking at each locker separately, we now consider the entire set together.

M1 will be the product of all the modulus except 3, so 35. M2 will be the product of all the small modulus except 5, and M3 will be the product of all the 3 modulus except 7.

Next, we calculate M1, M2, and M3 as follows: M1 = 5 * 7 = 35, M2 = 3 * 7 = 21, and M3 = 3 * 5 = 15. These values represent the product of the remaining moduli, which are used to calculate the necessary inverses in the next steps.

If each locker has a different number of keys, M1, M2, and M3 represent the keys available if we take away one key type (modulus) for each locker system. We need to consider how many unique keys we still have to work with for each locker.

Now, my next goal will be to find M inverse modulo m1, M inverse modulo m2 and M inverse modulo m3, which I can do by using extended Euclid’s algorithm.

Using the Extended Euclidean Algorithm, we calculate the inverses: M1^(-1) mod 3, M2^(-1) mod 5, and M3^(-1) mod 7. These inverses are crucial because they help us construct the final solution that satisfies all the initial congruences.

Finding these inverses is like determining which exact combinations or adjustments (keys) will help unlock each locker when you have multiple access points (moduli) to consider.

So, then as per the Chinese remainder theorem, we will compute the value x which is the linear combination of your a1, a2, and a3 and the linear combiners are the various m1, m2, m3 and their respective multiplicative inverse multiplied with each other, so this will be the value of x = 2 * 35 * 2 + 3 * 21 * 1 + 2 * 15 * 1 mod 105.

We calculate the final solution x as follows: x = 2352 + 3211 + 2151 mod 105. This gives us a combination of the remainders with their corresponding moduli adjusted by their inverses. The final x will yield a number that satisfies all original constraints.

Think of combining all the unique keys (results from each modulus) to create a single master key (final x) that can open all lockers (satisfy all congruences).

Now this x will be 233 modulo 105 so, our goal is to find out the unique solutions of course, 233 is a solution if I take x = 233 you can verify that it satisfies the system of linear equation, but we want to find out a unique solution in the range 0 to 104.

Once we compute x = 233, we need to ensure it lies within the range of the modulus M (0 to 104). To do this, we can compute 233 mod 105, which gives us 23. This is now our unique solution, satisfying all initial equations.

You can think of this step as fitting your combined master key back within a predetermined lock (the range of possible solutions). The number 23 is the key that works for all and is neatly placed within the boundaries set by our original question.

So now, let us see some application of Chinese Remainder Theorem, it has tremendous applications, of course in cryptography, but in general it has other applications and our main application is when we want to do arithmetic with large values.

The Chinese Remainder Theorem is particularly useful in computer science and cryptography since it allows the manipulation of large numbers by reducing them to simpler calculations with smaller moduli. Instead of handling gigantic numbers directly, we can work with their smaller equivalents and combine the results to gain efficiency.

Imagine you have a long calculation that would normally take a lot of time to compute, but you can break it down into smaller parts, solve those quickly, and combine the results. It's like carrying a heavy load across a distance; instead of one large bag, you use several smaller, lighter bags that are easier to manage.

--