Search for a tool
Chinese Remainder

Tool to compute congruences with the chinese remainder theorem. The Chinese Remainder Theorem helps to solve congruence equation systems in modular arithmetic.

Results

Chinese Remainder -

Tag(s) : Mathematics, Arithmetics

dCode and you

dCode is free and its tools are a valuable help in games, puzzles and problems to solve every day!
You have a problem, an idea for a project, a specific need and dCode can not (yet) help you? You need custom development? Contact-me!

Team dCode read all messages and answer them if you leave an email (not published). It is thanks to you that dCode has the best Chinese Remainder tool. Thank you.

# Chinese Remainder

## Chinese Remainder Calculator

Tool to compute congruences with the chinese remainder theorem. The Chinese Remainder Theorem helps to solve congruence equation systems in modular arithmetic.

### What is the Chinese Remainder Theorem ?

The Chinese remainder theorem is the name given to a system of congruances (modular equations). The original problem is to consider a number of elements which we know the remainder of their Euclidean division.

Example: If they are arranged by 3 there remains 2. If they are arranged by 5, there remain 3 and if they are arranged by 7, there remain 2. How many objects are there?

Consider a list of $$k$$ coprimes integers $$n_1, ..., n_k$$ and their product $$n = \prod_{i=1}^k n_i$$. For all integers $$a_1, ... , a_k$$, it exists another integer $$x$$ which is unique modulo $$n$$, such as :

$$\begin{matrix} x \equiv a_1\pmod{n_1} \\ \ldots \\ x \equiv a_k\pmod{n_k} \end{matrix}$$

### How to calculate chinese remainder?

To find a solution of the congruence system, consider the numbers $$\hat{n}_i = \frac n{n_i} = n_1 \ldots n_{i-1}n_{i+1}\ldots n_k$$ which are also coprimes. To find the modular inverses, use the Bezout theorem to find integers $$u_i$$ and $$v_i$$ such as $$u_i n_i + v_i \hat{n}_i = 1$$. Here, $$v_i$$ is the modular inverse of $$\hat{n}_i$$ modulo $$n_i$$.

Consider then the numbers $$e_i = v_i \hat{n}_i \equiv 1 \mod{n_i}$$. A particular solution of the Chinese remainders theorem is $$x = \sum_{i=1}^k a_i e_i~$$

dCode accepts numbers as pairs (remainder, modulo), but the simplest is to write x = A mod B

Example: $$(2,3),(3,5),(2,7) \iff \left\{ \begin{array}{ll} x = 2 \mod 3 \\ x = 3 \mod 5 \\ x = 2 \mod 7 \end{array} \right. \Rightarrow x = 23$$