Chinese Remainder Theorem

Introduction:

The Chinese remainder theorem is commonly employed in large integer computing because it permits a computation bound on the size of the result to be replaced by numerous small integer computations. This remainder theorem definition provides an effective solution to major ideal domains.

According to the Chinese remainder theorem, every primary ideal domain is actual (expressed in terms of congruences). It has been generalized to any ring using a two-sided ideal formulation.

Bezout’s Identity or Bezout’s Lemma:

Bézout’s identity (also known as Bézout’s lemma) is the following theorem, named after Étienne Bézout:

Assuming a and b to be integers or polynomials with d as the greatest common divisor, we then have, x and y to be integers or polynomials such that ax + by = d. Furthermore, all integers or polynomials of the type az + bt are multiples of d.

Chinese Remainder Theorem Definition: 

Under the assumption that the divisors are pair-wise co-prime, the Chinese remainder and factor theorem asserts that if one knows the remainder of the Euclidean division of an integer n by multiple integers.

One can uniquely determine the remainder of the division of n by the product of these numbers (no two divisors share a common factor other than 1).

Statement of the Remainder Theorem:

The Chinese Remainder Theorem states that:

According to pair: n1, n2,…, nk and arbitrary integers a1​, a2​,…, ak the system of simultaneous congruences is given co-prime positive integers.

As a result, x is unknown; instead of knowing x, we know the residual after dividing x by a set of numbers. The equations have precisely one solution if the integers ni are pair-wise co-primes (that is, each one is co-prime with all the others). Modulo N will be the solution, with N equal to the product of all ni.

x​≡a1​(mod n1​)

x​≡a2​(mod n2​)

.

.

.

x​≡ak​(mod nk​)​, has a solution, and the solution is unique modulo N=n1​n2​⋯nk​.

Proof of the Chinese Remainder Theorem:

To see why x is a solution, for each i=1,2,…,k, we have

x​≡(a1​y1​z1​+a2​y2​z2​+⋯+ak​yk​zk​)(mod ni​),

x ≡ai​yi​zi(mod ni)

​ x ≡ai​​(mod ni),

The second line follows since yj≡0 (mod ni), for each j is not equal to i, and the third line follows yi​zi≡1(mod ni)

Now, suppose there are two solutions u and v to the system of congruences. Then  n1​∣(u−v), n2​∣(u−v),…, nk​∣(u−v), and since n1​n2​⋯nk​ are relatively prime, we have that  n1​n2​⋯nk​ divides u−v, or u≡v(mod n1​n2​⋯nk).

Thus, the solution is a unique modulo n1​n2​⋯nk.

Also, there is another way of proving this remainder theorem effectively:

Proof: Let p1=p−1 (mod q) and q1=q−1(mod p). These must exist since p, q are co-prime. Then we assert that it is an integer, then

y=aqq1+bpp1 (mod pq); then both equations are satisfied with y:

Modulo p, we have y=aqq1=a (mod p) since qq1=1(mod p). Similarly, y=b(mod q). Thus y is a solution for x.

Now we have to show that no other solutions exist modulo pq. If z=a(mod p) then z−y is a multiple of p. If z=b(mod q) as well, then z−y is also a multiple of q. Since p and q are co-prime, this implies z−y is a multiple of pq, hence z=y(mod pq). 

This remainder theorem implies we can represent an element of Zpq by one element of Zp and one element of Zq, and vice versa. In other words, we have a bijective function between Zpq and Zp×Zq.

How to Solve the System of Congruences with Chinese Remainder Theorem:

Begin the congruence with the largest modulus and re-write it as an equation for some positive integer. Substitute the equation for x in this congruence with the next largest possible modulus and solve the congruence equation for the value of the integer for which you found out the largest modulus. Re-framing the solved congruence as an equation, substitute the equation for the integer into the value of x. Continue this process until the system of congruences is satisfied.

Problems on Chinese Remainder Theorem:

Example 1: Find x, if possible, such that 2x ≡ 5 (mod 7), and 3x ≡ 4 (mod 8)

 Solution: First, we must know that 2 has an inverse modulo 7, namely 4. 

So we can write the first equivalence as 

x ≡ 4 · 5 ≡ 6 (mod 7). (Using the Chinese Remainder Theorem)

Hence, we have that:  x = 6 + 7k for some k ∈ Z. 

We can now use this in place for the second equivalence: 

3x ≡ 4 (mod 8) 3(6 + 7k) ≡ 4 (mod 8) 18 + 21k ≡ 4 (mod 8) 2 + 5k ≡ 4 (mod 8) 5k ≡ 2 (mod 8). 

Again, noting that 5 has an inverse modulo 8, namely 5, we thus obtain k ≡ 10 ≡ 2 (mod 8). Hence, we have that k = 2 + 8j for some j ∈ Z. 

Using this result back again for x, we have that x = 6 + 7k = 6 + 7(2 + 8j) = 20 + 56j for some j ∈ Z. In fact, any choice of j will work here. Hence, we have that x is a solution to the system of congruences if and only if x ≡ 20 (mod 56). 

Example 2:  Find x, if possible, such that x ≡ 3 (mod 4), and x ≡ 0 (mod 6). 

Solution: We will approach this problem the same way, using this remainder and factor theorem as we did above. From the first equivalence, we have that x = 3 + 4k for some k ∈ Z. Then, the second equivalence implies that 3 + 4k ≡ 0 (mod 6), and hence 4k ≡ −3 ≡ 3 (mod 6). However, this is impossible since we know that gcd(4, 6) = 2 and 2 6 |3.

Prime Powers First

The remainder and factor theorem has the significant consequence that when studying modular arithmetic in general, we can learn modular arithmetic to a prime power first and then use the Chinese Remainder Theorem to extend any results. For any integer n, we factorize n into primes n=p1k1…pmkm and then use the Chinese Remainder Theorem to get

Zn=Zp1k1×…×Zpmkm

To prove statements in Zpk, one starts from Zp and inductively works up to Zpk. Thus the most important case to study is Zp.

Conclusion:

Using the Chinese Remainder Theorem, you can solve congruences and inequalities more efficiently than any remainder theorem or factor theorem. The Chinese Remainder Theorem aids in solving coding equations in C, C++, and Java.