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) : Arithmetics

Share dCode and more

dCode is free and its tools are a valuable help in games, maths, geocaching, puzzles and problems to solve every day!
A suggestion ? a feedback ? a bug ? an idea ? Write to dCode!

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!

Thanks to your feedback and relevant comments, dCode has developed the best 'Chinese Remainder' tool, so feel free to write! Thank you!

# Chinese Remainder

## Chinese Remainder Calculator

 Display The smallest (positive) solution All solution in general form (if possible)

### What is the Chinese Remainder Theorem?

The Chinese remainder theorem is the name given to a system of congruences (multiple simultaneous modular equations). The original problem is to calculate a number of elements which remainders (of their Euclidean division) are known.

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? This exercise implies to calculate $x$ such that $x \equiv 2 \mod 3$ and $x \equiv 3 \mod 5$ and $x \equiv 2 \mod 7$

Take 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, take 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$.

Take 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 A, modulo B) in equations of the form 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$

### When does the Chinese Remainder Theorem have no solution?

The system of equations with remainders $r_i$ and modulos $m_i$ has solutions only if the following modular equation is true: $$r_1 \mod d = r_2 \mod d = \cdots r_n \mod d$$ with $d$ the GCD of all modulos $m_i$.

## Source code

dCode retains ownership of the online "Chinese Remainder" tool source code. Except explicit open source licence (indicated CC / Creative Commons / free), any "Chinese Remainder" algorithm, applet or snippet (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any "Chinese Remainder" function (calculate, convert, solve, decrypt / encrypt, decipher / cipher, decode / encode, translate) written in any informatic language (Python, Java, PHP, C#, Javascript, Matlab, etc.) and no data download, script, copy-paste, or API access for "Chinese Remainder" will be for free, same for offline use on PC, tablet, iPhone or Android ! dCode is free and online.

## Need Help ?

Please, check our dCode Discord community for help requests!
NB: for encrypted messages, test our automatic cipher identifier!