Chinese remainder theorem

In this post I would like to talk about the Chinese Remainder Theorem. You might have heard this problem as a kid: There are x number of things. When taken in groups of 5, they leave a remainder 1. When taken in groups of 7, they leave a remainder 2. When taken in groups of 9, they leave a remainder 3. And when taken in groups of 11, they leave a remainder 4. Find the value of x. We will see how such problems can be solved using the Chinese Remainder Theorem(CRT).

LINEAR CONGRUENCES

Lets talk about linear congruences. You might have already encountered them informally in my previous post on the RSA encryption system. Here I would like to introduce it a bit more formally.

ax ≡ b (mod n)

Abusing the use of notation, we can express this equation into a form which might look more familiar, i.e ax%n = b. In other words, the integer ax when divided by n leaves a remainder equal to b.

Lets say that we find a solution to the above equation, say x = x₀.
=> ax₀ ≡ b (mod n)
=> n | (ax₀ - b) (where | stands for divide)
=> ax₀ - b = ny₀
=> ax₀ - ny₀ = b ..... (1)

Hence the linear congruence equation reduces to the well known diophantine equation. If you are familiar with the diophantine equation, feel free to skip the next part.

DIOPHANTINE EQUATION

The most general form of the diophantine equation is: ax + by = c

Lets try to analyse this equation for integer solutions. 

It is easy to see that this equation will have infinite integer solutions as it is the equation of a line. Hence all the integer (x, y) points on the line, will satisfy this equation.

But it might be the case that this equation does not possess any integer solution. This can happen when the line does not pass through any integer (x, y) coordinate. Let us try to find that condition mathematically.

Let, d = gcd(a, b) hence a = rd and b = sd where gcd(r, s) = 1

Replacing the value of a and b in the original diophantine equation, we get, 

=> rdx + sdy = c 

=> d(rx + sy) = c

=> d | c (As c/d is an integer from the above equation)

Hence the condition for the diophantine equation ax + by = c to have integer solution is d | c, where d = gcd(a, b).

Now lets find the family of solution for the diophantine equation. Lets say that we have found a solution (x₀, y0) for the equation. Now we want to find another solution say (x', y')

=> ax₀ + by₀ = ax' + by' = c
=> a(x' - x₀) = b(y₀ - y')
=> rd(x' - x₀) = sd(y₀ - y')   (d = gcd(a, b))
=> r(x' - x₀) = s(y₀ - y')
=> r | s(y₀ - y')
=> r | (y₀ - y')   (as gcd(r, s) = 1) .... (2)

Similarly
=> s | (x' - x₀)    .... (3)

From (3), we have

=> x' - x₀ = st
=> x' = x₀ + st (where b = ds, so s = b/d)
=> x' = x₀ + (b/d).t .... (4)

And from (2) we get,
y' = y₀ - (a/d).t .... (5)

Hence from (4) and (5), we get the complete solution for the diophantine equation.

BACK TO LINEAR CONGRUENCE

Having studied the diophantine equation, we can start our analysis of equation (1) now, which was ax0 - ny0 = b

Through a direct comparison with the diophantine equation, we have the following condition for the existence of integer solution to this equation

d | b, where d = gcd(a, n)

Moreover the family of solution for x can be given as, 

x₀, x₀ + n/d, x₀ + 2.n/d, ....., x₀ + t.n/d ........ (6)

It is worth noting that we are now solving a congruence modulo n. Hence there will be finite number of unique solutions. We claim that there will be only d number of unique solutions. In other words, equation (6) should have a constraint 0 <= t < d, for all solutions to be unique.

First we will prove uniqueness of any two solution in this range. Let, x₀ + (n/d).t1 and x₀ + (n/d).t2 be the two solution such that 0 <= t1 < t2 <= d-1.
We have to prove that these two solutions cannot be congruent modulo n.

We will prove this by contradiction. Let us assume that the two solutions are congruent modulo n. Hence,
=> x₀ + (n/d).t1 ≡ x₀ + (n/d).t2 (mod n)
=> (n/d).t1 ≡ (n/d).t2 (mod n)
=> (n/d).(t1 - t2) = ny
=> (t1 - t2) = nd
=> t1 ≡ t2 (mod d) ... (7)

From (7), we have that d | (t1 - t2) or d | (t2 - t1)
But since 0 <= t1 < t2 <= d-1, hence 0 < t2 - t1 < d. So there is no way in which d divides (t2 - t1). So d ∤ (t2 - t1), which is a contradiction. Hence all the d solutions are unique.
Now it remains to be proved that ∀ t >= d, the solutions are not unique.
Let t = q.d + r where r = {0, 1, ..... d-1}
So, x₀ + (n/d).t = x₀ + (n/d).(q.d + r)
=> x₀ + nq + (nr/d)
=> x₀ + (n/d).r (mod n)
And as 0 <= r < d, hence this is one of the d unique solutions we already found.

Hence the linear congruence ax ≡ b (mod n) has integer solutions only when d | b, where d = gcd(a, b) and it has exactly d unique solutions given as:

x₀, x₀ + (n/d), x₀ + (2n/d), ...., x₀ + ((d-1).n/d)

SYSTEM OF SIMULTANEOUS LINEAR CONGRUENCE

Having studied about a linear congruence in depth, lets move our focus to a system of such equations. 

a₁x ≡ b₁ (mod n₁)
a₂x ≡ b₂ (mod n₂)
a₃x ≡ b₃ (mod n₃)

.

.

a_rx ≡ b_r (mod n_r)

Now for the above system of congruences to have a soution, each of the linear congruences should have a solution individually.
So if we consider d_k = gcd(a_k, n_k) ∀ k∈{0, 1... r}, d_k | b_k. Moreover, we assume that gcd(n_i, n_j) = 1 i.e the n's are relatively prime to each other.
Now lets go back to the question we asked during the beginning of the post. If we try to formulate that question in terms of congruences, we will have the following system of linear equations.

x ≡ 1 (mod 5)
x ≡ 2 (mod 7)
x ≡ 3 (mod 9)
x ≡ 4 (mod 11)

We have to solve for x.

CHINESE REMAINDER THEOREM

CRT aims at solving the type of linear congruence systems as described by the above problem. CRT states that:
For a system of linear congruences of the form

x ≡ b₁ (mod n₁)
x ≡ b₂ (mod n₂)
x ≡ b₃ (mod n₃)

.

.

x ≡ b_r (mod n_r)
where gcd(n_i, n_j) = 1, it will always have a unique solution modulo n = n1.n2.n3...nr.

Lets try to prove the CRT and find that unique solution.

Proof: I will give more of an informal proof for the CRT as the formal one is pretty unintuitive. Let us begin by thinking of an integer which can satisfy all the above linear congruences. (We can be sure that each linear congruence will have a solution as a_i = 1 for each equation and gcd(1, n_i) = 1 and 1 | b_i)
Now the value x should be such that it produces the remainder b_i's when divided by the corresponding n_i's. Hence, it becomes clear that the solution must contain r terms most probably added together. Now when divided by a particular n_i only one term should produce the remainder. Rest all the terms should evaluate to zero.
Hence we introduce another variable
Nk = n₁.n₂....n_k-1.n_k+1....n_r
So it is the product of all the numbers except n_k.
Moreover the term which remains should produce the remainder a_k. So if we consider the solution to be of the form a₁N₁ + a₂N₂ + .... + a_rN_r.
We have the number remaining when take modulo n_k as a_kN_k (mod n_k). However we wanted the modulo to be just a_k. So we need to somehow get rid of the N_k.
Well, we can define another linear congruence equation:
N_k.x ≡ 1 (mod n_k) .... (8)
The above equation provides a method of finding the modular multiplicative inverse of an integer. (N_k in this case)
Let us say that the above equation has a solution x = x_k (Again we can check that it has just one unique solution using the argument proved before). Hence we have that N_k.x_k ≡ 1 (mod n_k) and so N_k.x_k.a_k ≡ a_k (mod n_k), which is what we wanted.
So now we can construct the final solution as:
x' = a₁N₁x1 + a₂N₂x2 + .... + a_rN_rx_r
It is easy to verify that the above solution satisfies all the linear congruences individually.
As for the argument of this solution being unique, let us assume that there exists another solution x'' such that x' ≢ x'' (mod n) (where n = n1.n2.n3...nr)
Now as both x' and x'' are solutions to the system, hence we can say that:
x' ≡ a_k ≡ x'' (mod n_k)
=> n_k | x' - x''
So we have n₁ | x' - x'', n₂ | x' - x''.... n_r | x' - x''
We can combine all these to give n | x' - x'' (as gcd(n_i, n_j) = 1)
=> x' - x'' ≡ 0 (mod n)
=> x' ≡ x'' (mod n)
Which is a contradiction and hence the two solutions are congruent. So there is just one unique solution of the CRT, which is
x' = a₁N₁x1 + a₂N₂x2 + .... + a_rN_rx_r

Now lets finally go back to the problem posed at the start.
x ≡ 1 (mod 5)
x ≡ 2 (mod 7)
x ≡ 3 (mod 9)
x ≡ 4 (mod 11)

We have to solve the above set of linear congruences. Using CRT, we have
N₁ = 7.9.11 = 693
N₂ = 5.9.11 = 495
N₃ = 5.7.11 = 385
N₄ = 5.7.9 = 315
and a₁ = 1, a₂ = 2, a₃ = 3 and a₄ = 4
Also we have to solve
693.x₁ ≡ 1 (mod 5)
495.x₂ ≡ 1 (mod 7)
385.x₃ ≡ 1 (mod 9)
315.x₄ ≡ 1 (mod 11)
Using brute-force we can obtain x₁ = 2, x₂ = 3, x₃ = 4, x₄ = 8.
Hence the final solution is:
x' = 1.693.2 + 2.495.3 + 3.385.4 + 4.315.8
    = 19056

Taking the final solution modulo n (where n = 5.7.9.11 = 3465), we have

19056 ≡ 1731 (mod 3465) 
Hence 1731 is the required unique solution which is the smallest too.