Restes Chinois

Le théorème des restes chinois est le nom donné à un système de congruences simultanées (équations modulaires multiples). Le problème original consiste à considérer un certain nombre d'éléments dont les restes de leurs divisions euclidiennes sont connus.

Soient une liste de $ k $ entiers $ n_1, ..., n_k $ premiers entre eux et leur produit $ n = \prod_{i=1}^k n_i $. Pour tous entiers $ a_1, ... , a_k $, il existe un autre entier $ x $ qui est unique modulo $ n $, tel que :

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

Pour trouver une solution au système de congruences, considérer les nombres $ \hat{n}_i = \frac n{n_i} = n_1 \ldots n_{i-1}n_{i+1}\ldots n_k $ qui sont aussi premiers entre eux. Pour trouver les inverses modulaires, utiliser le théorème de Bézout pour trouver des entiers $ u_i $ et $ v_i $ tels que $ u_i n_i + v_i \hat{n}_i = 1 $. Ici, $ v_i $ est l'inverse de $ \hat{n}_i $ modulo $ n_i $.

Considérer alors les nombres $ e_i = v_i \hat{n}_i \equiv 1 \mod{n_i} $. Une solution particulière du théorème des restes chinois est $$ x = \sum_{i=1}^k a_i e_i $$

Le programme accepte les nombres sous forme de couples (reste A, modulo B) dans les équations de la forme x = A mod B

Le système d'équation avec des restes $ r_i $ et des modulos $ m_i $ a des solutions uniquement si l'équation modulaire suivante est vérifiée : $$ r_1 \mod d = r_2 \mod d = \cdots r_n \mod d $$ avec $ d $ le PGCD de tous les modulos $ m_i $.