Can anyone please explain me the Chineese remainder theorem. I want to learn chineese remainder theorem referred to some sources like wikipedia but I am finding it really complicated. Can anyone please explain it in easy way.
I will try to explain it with an example.
So, there’s some linear congruences given,
x = 2(mod 3)
x = 2(mod 4)
x = 1(mod 5)
you’ll have to find x.
Remember these divisors should be pairwise co-prime. That means gcd(3,4) = 1, gcd(3,5) = 1, gcd(4,5) = 1
Now here’s the first step.
mod 3 mod 4 mod 5
x = + +
What this means we’ll have a number x which will be divided by every divisor.
So, at first we want a number modulo 3. What to do?
x = + 3 + 3 (the 2nd and 3rd section will disappear if we modulo it by 3)
Like this, do these steps.
x = 4 + 3 + 3*4
x = 4*5 + 3*5 + 3*4
x = 20 + 15 + 12
Now we will modulo it by 3,4,5 respectiely,
x = 20(mod 3) = 2(mod 3) ; got it!
x = 15(mod 4) = 3(mod 4) ; didn't get it!
x = 12(mod 5) = 2(mod 5) ; didn't get it!
So, what now? we have to multiply some values, so that we get 2(mod 4) and 1(mod 5).
remember from extended euclid, we can determine, n*x = 1(mod m); if we know n and m.
So, from extended euclid, we get 3 * 3 = 1(mod 4), 2 * 3 = 1(mod 5)
So, the final answer will be,
x = 20 + 15*3*2 + 12*3 (2 is multiplied in the 2nd section as we need 2(mod 4) )
x = 146 which is one answer of infinitely many answers.
1 Like
The CRT is about a system of congruences. Such a system looks like this:
x = a_1 ~(\text{mod } m_1)\\
x = a_2 ~(\text{mod } m_2)\\
\vdots\\
x = a_n ~(\text{mod } m_n)
The theorem says, that this system has a unique solution \text{mod } M := m_1m_2\dots m_n if the moduli m_i are coprime.
Now, this already might be interesting to you. But to actually do something with it, you probably want to compute this unique solution. Luckily there exists a formula for this solution:
x = \sum_{i=1}^n a_i b_i c_i ~(\text{mod }M),
where b_i := M / m_i and c_i := b_i^{-1} (\text{mod }m_i).
Before I’ll give an example, let me quickly show you why this is a solution. It’s quite easy. To check it, we only have to look if this x satisfies all n congruences from above. Let’s check if the j th is satisfied.
x ~(\text{mod }m_j) = \sum_{i=1}^n a_i b_i c_i ~(\text{mod }M)~(\text{mod }m_j) = \sum_{i=1}^n a_i b_i c_i ~(\text{mod }m_j)
Because b_i = 0 ~(\text{mod }m_j) for all i \ne j it further follows:
= a_j b_j c_j ~(\text{mod }m_j) = a_j b_j b_j^{-1} ~(\text{mod }m_j) = a_j ~(\text{mod }m_j)
So x is really a solution for the j th congruence.
Notice, that the CRT also guarantees, that only 1 solution exists (\text{mod }M). This is also easy to prove. Lets say you have two different solutions x and y. Since x = a_i ~(\text{mod }m_i) and y = a_i ~(\text{mod }m_i), it follows that x - y = 0 ~(\text{mod }m_i) and therefore x - y = 0 ~(\text{mod }M) or x = y ~(\text{mod }M). So x and y are actually not different solutions.
Now to an example. This is the classical problem from Sunzi Suanjing (a chinese mathematician from the 3rd century):
There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there?
To translate this to modern English we get the following problem: There is a pile with x stones. If we group them into piles of 3 stones each, then 2 will remain. If we group them into piles of 5 stones each, then 3 will remain. And if we group them into piles of 7 stones, then 2 will remain. This translates into the system of congruences:
x = 2 ~(\text{mod }3), ~x = 3~(\text{mod }5), ~x = 2 ~(\text{mod }7)
Since we have the formula for x, we can directly compute the solution. b_1 = 5\cdot7 = 35~, b_2 = 3\cdot 7 = 21~, b_3 = 3\cdot 5 = 15~.
c_1 = 35^{-1} ~(\text{mod }3) = 2^{-1} ~(\text{mod }3) = 2~,
c_2 = 21^{-1} ~(\text{mod }5) = 1^{-1} ~(\text{mod }5) = 1~,
c_3 = 15^{-1} ~(\text{mod }7) = 1^{-1} ~(\text{mod }7) = 1~.
Normally you have to apply some tricks to compute the modular inverse. In this example I was able to guess them, but if there are bigger numbers involed you have to compute them with the a^{-1} = a^{m-2} trick or with the extended Euclidean algorithm.
So we get the result:
x = 2\cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 = 140 + 63 + 30 = 233 = 23 ~(\text{mod }105)
The solution is 23. Notice, the solution is only unique \text{mod }M. There are also infinitely many other solutions of the form 23 + k\cdot 105 like 23 + 105 = 128, or 23 + 8*105 = 863 or 23 - 2*105 = -187.
And one more infos: If the moduli m_i are not coprime, than you can’t really say anything about the solution. Sometimes there exists a unique solution \text{mod }lcm(m_1, m_2, \dots, m_n), sometimes there doesn’t exist one. For instance the following system doesn’t have a solution:
x = 2 ~(\text{mod }6), x = 3 ~(\text{mod }4)
Because the first congruence implies that x is even, and the second one implies that x is odd.
2 Likes
Sorry for writing another comment because I thought the previous one was getting quite big, and it’d be best if I only explained the example there. Now, we’ll derive the formula from the example (Sorry for wrong formatting):
So there are a series of linear congruences like the above example:
x = a1(mod m1)
x = a2(mod m2)
x = a3(mod m3)
.....
x = ak(mod mk)
What was our first step? We took k sections and multiplied them with divisors, excluding itself. So from this, we’ll get:
x = m2*m3*...*mk + m1*m3*....*mk + m1*m2*....*mk + .... + m1*m2*m3*...m(k-1)
Now, we checked for every section if it met our congruence or not. The easiest way here to use extended euclid here, to make all the sections like this 1(mod m1), 1(mod m2), 1(mod m3),…,1(mod mk)
Suppose, from extended euclid, we find y1,y2,y3,…,yk. So, now we’ll get:
x = m2*m3*...*mk*y1 + m1*m3*....*mk*y2 + m1*m2*....*mk*y3 + .... + m1*m2*m3*...m(k-1)*yk
Now, it’s the final step. Just multiply the sections with ai, so now we’ll get:
x = m2*m3*...*mk*y1*a1 + m1*m3*....*mk*y2*a2 + m1*m2*....*mk*y3*a3 + .... + m1*m2*m3*...m(k-1)*yk*ak
It’s the elaborate formula. The formulas you’ll see in the books are only the beautiful and compact version of this, but they are hard to understand.