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

Chinese Remainder - dCode

Tag(s) : Arithmetics

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*!

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

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} $$

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 $

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 $.

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

Please, check our community Discord for help requests!

chinese,remainder,theorem,modulo,congruence,equation,coprime,division

Source : https://www.dcode.fr/chinese-remainder

© 2021 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaching / CTF.

Feedback

▲