# Chinese Remainder Theorem Calculator

The Chinese Remainder Theorem calculator offered by Mathematics Master is a tool that provides a solution to a system of simultaneous linear congruences with coprime moduli. It follows the principles of the Chinese Remainder Theorem, which states that for any given set of congruences, there will always be an x that satisfies all the specified congruences. Furthermore, when we have a pair of congruences with moduli that are relatively prime (meaning they have no common factors), we can solve the system in a unique manner.

$$x \equiv a \pmod b$$
$$x \equiv c \pmod d$$

## 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

What is a remainder theorem calculator?

A free online calculator, the Remainder Theorem Calculator, shows the specified polynomial equations’ quotient and the remainder of the division.

Why is it called the Chinese remainder theorem?

Chinese Remainder Theorem: An old theorem specifies the conditions under which many equations can simultaneously have an integer solution. Although the complete theorem was first presented in 1247 by Qin Jiushao, the theory has its roots in the work of the Chinese mathematician Sun Zi, who lived in the third-century a.d.

What is the factor theorem?

The factor theorem is applied in mathematics when factoring the polynomials. It is a theorem that connects the polynomial’s zeros and factors. For example, the factor theorem states that (x-a) is a factor of f(x) if f(a)=0 and f(x) is a polynomial of degree n one and ‘a’ is any real number. The factor theorem calculator is used to calculate the factor of division.