Chinese Remainder Theorem Calculator

What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem is a mathematical principle that states that a system of congruences, which are essentially a set of remaining equations, will always have a unique solution (in a certain sense). This theorem relies on the Euclidean method and Bézout’s identity, two fundamental concepts in number theory that are closely intertwined and play a crucial role in proving the Chinese Remainder Theorem.

The Euclidean method helps us compute the greatest common divisor between numbers, while Bézout’s identity establishes a relationship between the greatest common divisor and linear combinations of the numbers involved. Together, these concepts form the foundation for understanding and applying the Chinese Remainder Theorem.

Euclidean algorithm

A method for determining the GCD of two integers fast is the Euclidean Algorithm.

The Procedure

The following is the Euclidean algorithm for determining GCD\((A, B)\):

• If \(A = 0\) ; GCD \((A,B)=B\), since the GCD\((0,B)=B\), and we can stop.
• If \(B = 0\) ; GCD \((A,B)=A\), since the GCD\((A,0)=A\), and we can stop.
• In the quotient remainder form : \((A = B⋅Q + R)\)

Bézout’s identity

Bézout’s identity, sometimes known as Bézout’s lemma and named for Étienne Bézout, is as follows:

Bézout’s identity: Let a and b be integers with d being their greatest common factor. Then there are integers x and y such as \(ax + by = d\). In addition, the integers of the type \(az + bt\) are multiples of \(d\).

In this case, 0 is assumed to be the greatest common divisor of 0 and 0. The non-unique integers x and y are Bézout coefficients for \((a, b)\).

Statement of Remainder Theorem

The Chinese Remainder Theorem states that if we have a system of congruences with positive integers n1, n2, …, nk that are pairwise coprime (meaning they have no common factors), and corresponding integers a1, a2, …, ak, then there exists a unique solution for x modulo N, where N is the product of n1, n2, …, nk.

In simpler terms, if we have a set of equations where x is congruent to certain values modulo different numbers, and those numbers don’t have any factors in common, then we can find a solution for x that satisfies all the equations. This solution will be unique within a certain range determined by the product of those numbers.

Example Using Chinese Remainder Theorem

Using the Chinese Remainder Theorem to solve the following system: x ≡ 3 (mod 5) x ≡ 5 (mod 7)

We are given two congruences that we need to solve simultaneously.
x ≡ 3 (mod 5) x ≡ 5 (mod 7)

Apply the Chinese Remainder Theorem to compute N, N1, and N2

We calculate the value of N, N1, and N2 as follows:

\( N = 5 × 7 = 35 \)

\( N1 = \dfrac{N}{5} = \dfrac{35}{5} = 7\)

\( N2 = \dfrac{N}{7} = \dfrac{35}{7} = 5 \)

Calculate the inverses
Now, we find the inverses of N1 and N2 modulo their respective moduli.

For N1:
\( 7x_1 ≡ 1 (mod 5) \)

We observe that 7 ≡ 2 (mod 5), so we can rewrite the congruence as:
\( 2x_1 ≡ 1 (mod 5) \)

The inverse of 2 modulo 5 is 3, so \( x_1 ≡ 3 (mod 5) \).

For N2:
\( 5x_2 ≡ 1 (mod 7) \)

We find that 5 ≡ 1 (mod 7), so we can rewrite the congruence as:
\( 1x_2 ≡ 1 (mod 7) \)

The inverse of 1 modulo 7 is 1, so \( x_2 ≡ 1 (mod 7) \).

Calculate x using the Chinese Remainder Theorem

Using the Chinese Remainder Theorem formula:

\( x = N1x_1a_1 + N2x_2a_2 \)

Substituting the values we obtained:

\( x = 7 × 3 × 1 + 5 × 1 × 1 \)

\( x = 21 + 5 \)

x = 26

Reduce x modulo N
To obtain the solution modulo the product of the moduli (35), we take x ≡ 26 (mod 35).

Finally, simplifying the congruence:

x ≡ 26 (mod 35)

x ≡ 26 ≡ 33 (mod 35)

Hence, the solution to the system is x ≡ 33 (mod 35).

Application of the Chinese Remainder Theorem

• The Chinese Remainder Theorem Calculator is often used in computations involving large integers because it allows us to break down a complex computation into multiple simpler computations with small integers, where we have knowledge about the size of the results.
• In the field of mathematics, the Chinese Remainder Theorem has been used to create a numbering system for sequences, known as Godel numbering. This numbering system is used in the proof of Godel’s Incompleteness Theorems.

FAQs