Le théorème chinois

Publié le 14/02/17

Soit {n_1,n_2,\ldots,n_r} dans {\mathbb{N}^*}, premiers entre eux deux à deux, et {N=\displaystyle\prod\limits_{k=1}^{r}n_k}.
On considère {\varphi\colon\mathbb{Z}/N\mathbb{Z}\longrightarrow\displaystyle\prod\limits_{k=1}^{r}\mathbb{Z}/n_k\mathbb{Z}\;} définie par :
{\forall\, x\in\mathbb{Z}/N\mathbb{Z},\quad\varphi(x)=\left(x\!\!\!\mod n_1,\;x\!\!\!\mod n_2,\;\ldots,\;x\!\!\!\mod n_r\right)}\varphi est un morphisme d’anneaux, injectif car son noyau est réduit à {0}.
Il est donc bijectif pour des raisons de cardinal.
En particulier, pour tous entiers {a_1,\ldots,a_r} :{\exists\,!\,x\in[\![0,N-1]\!],\;(S): \begin{cases}x\!\!\!\mod n_1=a_1\cr x\!\!\!\mod n_2=a_2\cr\ldots\cr x\!\!\!\mod n_r=a_r\end{cases}}Ce résultat est communément appelé théorème chinois.

1. Une première expression de la solution x de (S)

Pour {i\ne j}, on note {u_{i,j}} et {u_{j,i}} tels que {u_{i,j}\,n_i+u_{j,i}\,n_j=1}

Pour {1\le j\le r}, on note {M_j=\displaystyle\prod\limits_{i\ne j}u_{i,j}\,n_i}.
On pose {x=\Bigl(\displaystyle\sum\limits_{j=1}^{r}a_jM_j\Bigr)\mod n}.
On va voir que l’entier {x} est l’unique solution du système {(S)}.

Pour tous {i\ne j}, on a {u_{i,j}\,n_i+u_{j,i}\,n_j=1} donc {u_{i,j}\, n_i\equiv 1\ (n_j)}.

Ainsi {M_j=\displaystyle\prod_{i\ne j}u_{i,j}\,n_i\equiv\begin{cases}0\ (n_i)\text{\ si\ }i\ne j\\1\ (n_j)\end{cases}}

On a donc : {\forall\, i\in[[1,r]],\,x=\displaystyle\sum\limits_{j=1}^{r}a_jM_j\equiv a_i\ (n_i)}.

Voici une fonction chinese formant le tableau des u_{i,j} puis le vecteur des m_j, avant de renvoyer la solution x du système de congruences :

Considérons par exemple le système de congruences :
\begin{array}{l}x\equiv 11\ (143)\quad x\equiv35 \ (223)\\\\x\equiv42 \ (199)\quad x\equiv17 \ (301)\\\\x\equiv 22\ (211)\end{array}On voit que la solution minimale de ce système est x= 74269611713.

On calcule également le produit N des n_j, pour vérifier que 0\le x\lt N :

On vérifie que l’entier x est effectivement solution du système de congruences :

2. Optimisation avec des schémas de Horner (S)

On va calculer la solution {x} de (S) avec deux schémas de Horner.

On pose {b_1=a_1}, puis {b_2=(a_2-b_1)u_{1,2}\ \mod\ n_2}, etc.

Plus généralement, on pose: {b_r=\left[\bigl(\bigr[(a_r-b_1)u_{1,r}-b_2\bigr]u_{2,r}-b_3\bigr)\cdots-b_{r-1}\right]u_{r-1,r}\ \mod\ n_r}On va montrer que la solution {x} s’écrit {x=\displaystyle\sum_{k=1}^{r}\Bigl(b_k\prod\limits_{i=1}^{k-1}n_i\Bigr)}.

Après développement, on constate que :
{b_j=\Bigl(a_j\displaystyle\prod_{i=1}^{j-1}u_{i,j}-\displaystyle\sum_{k=1}^{j-1}\bigl(b_k\prod\limits_{i=k}^{j-1}u_{i,j}\bigr)\Bigr)\mod\!\!\! n_j}D’autre part, les égalités {u_{i,j}\,n_i+u_{j,i}\,n_j=1} donnent {u_{i,j}\,n_i\equiv\!\!\!\mod\ n_j}.

On en déduit {b_j\displaystyle\prod_{i=1}^{j-1}n_i=\Bigl(a_j-\displaystyle\sum_{k=1}^{j-1}\bigl(b_k\displaystyle\prod_{i=1}^{k-1}n_i\bigr)\Bigr)\!\!\!\mod n_j}.

Pour tout k, posons alors {c_k=b_k\displaystyle\prod_{i=1}^{k-1}n_i}.

Ainsi {c_j\equiv\Bigl(a_j-\displaystyle\sum_{k=1}^{j-1}c_k\Bigr)\!\!\!\mod n_j}, donc {\displaystyle\sum_{k=1}^{j}c_k\equiv a_i\!\!\!\mod n_i}.

Conclusion: l’entier {x} solution du système {(S)} s’écrit :
{x=\displaystyle\sum_{k=1}^{r}c_k=\sum\limits_{k=1}^{r}\bigl(b_k\displaystyle\prod_{i=1}^{k-1}n_i\bigr)}Enfin, l’entier {x} peut être calculé au moyen du schéma de Horner suivant :
{\begin{array}{l}x=b_1+\bigl(b_2+\cdots\\\\\qquad+\bigl(b_{r-2}+(b_{r-1}+b_rn_{r-1})n_{r-2}\bigr)\cdots n_2\bigr)n_1\end{array}}On peut maintenant écrire la nouvelle version de la fonction chinese :

Elle est beaucoup plus simple et efficace que la précédente. On note en particulier qu’il n’est plus nécessaire d’utiliser de variable locale {n} pour y placer le produit des {n_k}, ni bien sûr le tableau local {M} utilisé dans la première version.

La principale qualité de cette deuxième méthode est que tous les calculs intermédiaires se font dans {[\![0,N-1]\!]}. Les seuls calculs de congruences se font modulo les {n_k} (et non plus modulo {n} comme dans la première version). C’est en particulier frappant dans le calcul final de la solution {x}, qui ne fait pas intervenir aucune congruence…

Reprenons le système de congruences :
\begin{array}{l}x\equiv 11\ (143)\quad x\equiv35 \ (223)\\\\x\equiv42 \ (199)\quad x\equiv17 \ (301)\\\\x\equiv 22\ (211)\end{array}On retrouve bien la solution x= 74269611713.