Chinese Remainder Theorem

Chinese Remainder Theorem is a mathematical principle that solves systems of modular equations by finding a unique solution from the remainder of the division. It is used in cryptography and computer science for efficient computation.

In this article, we will learn the meaning and definition of the Chinese Remainder Theorem, the history of the Chinese Remainder Theorem, the statement and proof of the Chinese Remainder Theorem and applications of the Chinese Remainder Theorem.

According to the Chinese Remainder Theorem, if in a given set of equations, each equation has a different number (say, n₁, n₂, …, n_k), and these numbers are all relatively prime to each other, and also have some numbers (say, a₁, a₂,…, a_k), then there is a unique solution (let’s call it x) that satisfies all the equations at once.

This solution is found modulo the product of all the numbers (N = n₁ · n₂ ·…· n_k). Therefore, x satisfies each equation by leaving the same remainder when divided by its corresponding number (n_i) as the given number (a_i).

The theorem also ensures the uniqueness of the solution, implying that any other solution (x’) is congruent to (x) modulo (N).

Chinese Remainder Theorem Definition

Chinese Remainder Theorem states that,

“If a number is divided by several other numbers that have no common factors, one can find the remainder when dividing by the product of those numbers.”

History of SunZi

The theory is about a mathematical principle, which is associated with Sun Zi, an ancient Chinese author. It was later expanded by Qin Jiushao. Sun Zi is famous for his writings on military strategies in ancient China. He is considered as one of the first to use practical thinking when studying international matters.

Theorem states that a system of simultaneous congruences, defined by pairwise coprime positive integers (n₁, n₂,…., n_k ) and arbitrary integers (a₁, a₂,…., a_k )

x ≡ a₁ (mod n₁)

x ≡ a₂ (mod n₂)

⦙

x ≡ a_k (mod n_k)

has a unique solution modulo (N = n₁ n₂ …. n_k)

To proof Chinese remainder theorem, let us find an integer (x) that satisfies: x ≡ a_i (mod n_i) for each (i = 1, 2,…., k).

We define (N_i = N/n_i).

Since (n_i) and (N_i) are coprime, according to Bézout’s identity, there are integers (s_i) and (t_i) such that:

s_i·n_i + t_i·N_i = 1

We set (y_i = t_i·N_i)

Now, let’s construct (x) as follows,

x = [Tex]\sum_{i=1}^k a_i \cdot y_i[/Tex]

This solution satisfies all the congruences, i.e., x ≡ ai (mod ni) for each (i). To see this, observe:

x ≡ a_i·y_i ≡ a_i·t_i·N_i ≡ a_i·1 ≡ a_i

Thus, (x) is a solution to the system of congruences.

Uniqueness:

Suppose (x) and (x’) are two solutions to the system of congruences. We aim to show that (x ≡ x’ (mod N).

Let (m = x’ – x). Since both (x) and (x’) satisfy all the congruences, (m) must also satisfy them. Therefore, (m) is divisible by each of the moduli (n₁, n₂,…., n_k).

By definition, (N = n₁ · n₂ ·….· n_k). As (m) is divisible by each (n_i), it is also divisible by (N), i.e., m ≡ 0 (mod N).

Hence, x ≡ x’ (mod N, establishing uniqueness).

Necessary Condition for Chinese Remainder Theorem

For the Chinese Remainder Theorem to work, the numbers we are dividing by must not have any common factors. So, if there are two numbers that are being divided by, say (m_i) and (m_j), then they can not common factors other than 1. That means their biggest shared factor, called the greatest common divisor is 1.

GCD(m_i, m_j) = 1

This condition ensures that the system of congruences is consistent and that the solution provided by the Chinese Remainder Theorem is unique modulo the product of the moduli. If the moduli are not pairwise coprime, then the theorem may not yield a solution, or the solution may not be unique. Therefore, pairwise coprimality is a fundamental requirement for the application of the Chinese Remainder Theorem.

Chinese Remainder Theorem Solution for Two Moduli

Chinese Remainder Theorem provides a solution for systems of congruences involving two moduli. Given two pairwise coprime moduli (m₁) and (m₂), and their respective residues (a₁) and (a₂), the theorem states that there exists a unique solution modulo (m₁ × m₂) for the system of congruences:
x ≠ a₁ mod m₁

x ≠ a₂ mod m₂

The solution can be found using the formula:

[Tex]x = a_1 + m_1 \left( \frac{{a_2 – a_1}}{{m_1}} \right) \left( \frac{{m_1^{-1}}}{{m_2}} \right) \ (\text{mod}\ (m_1 \times m_2)) [/Tex]

Where (m₁^-1) denotes the modular multiplicative inverse of (m₁) modulo (m₂). This inverse can be found using methods such as the Extended Euclidean Algorithm.

Chinese Remainder Theorem Solution for General Case

Chinese Remainder Theorem (CRT) provides a solution for a system of congruences with arbitrary moduli. Suppose we have a system of congruences:

[Tex]x \equiv a_1 \ (\text{mod}\ m_1)[/Tex]

[Tex]x \equiv a_2 \ (\text{mod}\ m_2)[/Tex]

⁞

[Tex]x \equiv a_n \ (\text{mod}\ m_n) [/Tex]

Where (m₁, m₂, …, m_n) are pairwise coprime moduli and (a₁, a₂, …, a_n) are the corresponding residues.

CRT states that there exists a unique solution modulo (M = m₁ × m₂ × … × m_n) for this system of congruences. The solution can be found using the formula:

[Tex]x \equiv \sum_{i=1}^{n} a_i M_i y_i \ (\text{mod}\ M)[/Tex]

Where (M_i = M / m_i) and (y_i) is the modular multiplicative inverse of (M_i) modulo (m_i).

Suppose we have the following system of congruences:

x ≡ 2 mod 3

x ≡ 3 mod 5

x ≡ 2 mod 7

Calculate M = 3 × 5 × 7 = 105

Then, we calculate (M₁ = 105 / 3 = 35), (M₂ = 105 / 5 = 21), and (M₃ = 105 / 7 = 15).

find the modular multiplicative inverses (y₁), (y₂), and (y₃) for (M₁), (M₂), and (M₃) modulo (m₁), (m₂), and (m₃), respectively

y₁ is the modular multiplicative inverse of 35 modulo 3, which is 2

y₂ is the modular multiplicative inverse of 21 modulo 5, which is 1

y₃ is the modular multiplicative inverse of 15 modulo 7, which is 1

Now, using the formula:

x ≡ 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 (mod 105)

x ≡ 140 + 63 + 30 mod 105)

x ≡ 233 mod 105)

So, the solution for the system of congruences is x ≡ 233 (mod 105)

Chinese Remainder Theorem Solution for Not Coprime Moduli

Chinese Remainder Theorem helps in solving systems of equations where the remainders are congruent, even if the numbers that are divisible by are not relatively prime. But when the divisors are not relatively prime, there might be more than one solution to the problem.

Suppose we have the following system of congruences:

x ≡ 2 (mod 4)

x ≡ 3 (mod 6)

Here, the moduli 4 and 6 are not coprime because their greatest common divisor (GCD) is 2

To find the solution using the Chinese Remainder Theorem, we proceed as follows:

1. Find the moduli product: Calculate (m = 4 × 6 = 24).

2. Find the residues: Divide each modulus by the product of the other moduli to find the residue:

4 × k ≡ 1 (mod 6)

6 × k’ ≡ 1 (mod 4)

In this case, (k = 1) and (k’ = 1) satisfy the congruences, so the residues are both 1

3. Calculate the solution: The solution (x) is given by:

x = a₁ × m₂ × k + a₂ × m₁ × k’ (mod m)

Plugging in the values:

x = 2 × 6 × 1 + 3 × 4 × 1…(mod 24)

x = 12 + 12…(mod 24)

x = 24…(mod 24)

x = 0

So, the solution for this system of congruences is x ≡ 0 (mod 24).

Applications of the Chinese remainder theorem are as follows:

• Simplifies modular arithmetic calculations by breaking them into smaller parts.

• Used in error detection and correction algorithms, enhancing data reliability in digital communication and storage.

• Integral to cryptographic algorithms like RSA for secure data transmission and protection.

• Employed in computer graphics for efficient image rendering and visual effects.

• Provides insights into number theory, aiding research in prime numbers and Diophantine equations.

• Coding theory helps create error-correcting codes, ensuring that data can be sent reliably without mistakes.

• It makes parallel computing easier by dividing tasks effectively among many processors.

• Public key cryptography depends on it to calculate private keys from public ones, adding extra security measures.

Example 1: Suppose a certain number leaves a remainder of 2 when divided by 3, a remainder of 3 when divided by 5, and a remainder of 2 when divided by 7. Find the smallest positive integer that satisfies these conditions using the Chinese Remainder Theorem.

Solution:

Let x be the number that satisfies all the given conditions:

• Remainder of 2 when divided by 3
• Remainder of 3 when divided by 5
• Remainder of 2 when divided by 7

Now, as per the Chinese Remainder Theorem, since the moduli (3, 5, and 7) are pairwise coprime, a unique solution modulo is lcm(3,5,7)=105

• x ≡ 2(mod 3)
• x ≡ 3(mod 5)
• x ≡ 2(mod 7)

The modular inverses for each modulus will be:

• For 3, the modular inverse of 3 modulo 5 is 2 as 3⋅2 ≡ 1(mod 5)
• For 5, the modular inverse of 5 modulo 7 is 3 as 5⋅3 ≡ 1(mod 7)
• For 7, the modular inverse of 7 modulo 3 is 1 as 7⋅1 ≡ 1(mod 3)

Now calculate for x:

x ≡ (2⋅3⋅5⋅2)⋅(2⋅3) + (3⋅5⋅7⋅3)⋅(3⋅7) + (2⋅3⋅5⋅2)⋅(1⋅1)…(mod 105)

On solving each term we get,

x ≡ 60+315+60(mod105)

x ≡ 435(mod105)

x ≡ 15(mod105)

∴ Smallest positive integer that satisfies the given conditions is x=15.

Q1. Solve the system of congruences:

x ≡ 2 (mod 3)

x ≡ 3 (mod 5)

x ≡ 2 (mod 7)

Q2. Solve the system of congruences:

x ≡ 1 (mod 2)

x ≡ 2 (mod 4)

x ≡ 3 (mod 5)

Q3. Determine the smallest non-negative integer (x) such that:

x ≡ 2 (mod 3)

x ≡ 3 (mod 5)

x ≡ 2 (mod 7)

Why is it Called Chinese Remainder Theorem?

This theorem is called as Chinese Remainder Theorem because it was documented by the Chinese mathematician Sunzi in the 3rd century AD.

What is Chinese Remainder Theorem in Cyber Security?

In cybersecurity, the Chinese Remainder Theorem is used in cryptographic systems to break down complex mathematical problems into simpler ones. It is useful in public-key cryptography, where large prime numbers are involved.

Is Chinese Remainder Theorem Unique?

Chinese Remainder Theorem is not unique in the sense that it is a mathematical theorem discovered by the Chinese mathematician Sunzi. However, its application in various fields, which includes number theory, cryptography, and computer science, shows its versatility and significance in problem solving.