$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Théorème des restes chinois

Formulation avec les congruences
Théorème : Prenons $m_1$, ..., $m_n$ des entiers supérieurs à 2 deux à deux premiers entre eux, et $a_1,\dots,a_n$ des entiers. Le système d'équations : $$ \left\{ \begin{array}{rcl} x&\equiv&a_1\ [m_1]\\ \vdots&\vdots&\vdots\\ x&\equiv&a_n\ [m_n]\\ \end{array} \right. $$ admet une unique solution modulo $M=m_1\times\cdots m_n$ donnée par la formule : $$x=a_1M_1y_1+\dots+a_nM_ny_N$$ où $M_i=M/m_i$ et $y_i\equiv M_i^{-1}\ [m_i]$ pour $i$ compris entre $1$ et $n$.

Exemple : Une bande de 17 pirates s'est emparée d'un butin composé de pièces d'or d'égale valeur. Ils décident de se les partager également, et de donner le reste au cuisinier chinois. Celui-ci recevrait alors 3 pièces. Mais les pirates se querellent, et six d'entre eux sont tués. Le cuisinier recevrait alors 4 pièces. Dans un naufrage ultérieur, seuls le butin, six pirates et le cuisinier sont sauvés, et le partage donnerait alors 5 pièces d'or à ce dernier. Quelle est la fortune minimale que peut espérer le cuisinier quand il décide d'empoisonner le reste des pirates?

Si $x$ est ce nombre, $x$ est le plus petit entier positif tel que : $$ \left\{ \begin{array}{rcl} x&\equiv&3\ [17]\\ x&\equiv&4\ [11]\\ x&\equiv&5\ [6]\\ \end{array} \right. $$ On applique le théorème chinois : on a $M=17\times 11\times 6=1122$, $M_1=66$, $M_2=102$, $M_3=187$. L'inversion de chaque $M_i$ modulo $m_i$ (par l'algorithme d'Euclide) donne $y_1=8$, $y_2=4$, $y_3=1$.

On obtient donc : $$x\equiv 3\times 66\times8+4\times102\times4+5\times187\times1\ [1122] \equiv 785\ [1122].$$ Le gain minimal est de 785 pièces d'or, voila qui est particulièrement motivant!

Formulation avec $\mathbb Z/n\mathbb Z$
Théorème : Soient $m_1,\dots,m_k$ des entiers premiers entre eux deux à deux et $m=m_1\times m_2\times \cdots\times m_k$. Alors l'application $$\begin{array}{rcl} \phi:\mathbb Z/m\mathbb Z&\to&(\mathbb Z/m_1\mathbb Z)\times\dots\times (\mathbb Z/m_k\mathbb Z)\\ \overline{n}^{[m]}&\mapsto& (\overline{n}^{[m_1]},\dots,\overline{n}^{[m_k]}) \end{array},$$ où $\overline{n}^{[d]}$ désigne la classe de $n$ dans $\mathbb Z/d\mathbb Z,$ est bien définie et est un isomorphisme d'anneaux.
On peut se poser la question de savoir pourquoi ce théorème s'appelle théorème des restes "chinois". Cela est sans doute dû au fait que ce problème a été posé, pour la première fois, dans l'ouvrage Sunzi Suanjing, qu'on peut traduire en « Le classique mathématique de Maître Sun », écrit entre le 3è siècle et le 5è siècle après JC par le mathématicien chinois Sun Zi. Il l'énonce sous la forme suivante :
Il y a certaines choses dont le nombre est inconnu. Si on les compte par 3, il en reste 2; par 5, il en reste 3; par 7, il en reste 2. Combien y-a-t-il de ces choses?
Sun Zi donne le plus petit entier naturel solution de ce problème (23), sans donner un énoncé général ni fournir un algorithme amenant à cette solution. La première solution complète semble encore due à un mathématicien chinois, Ch'in Chiu-shao, dans son Traité mathématique en neuf parties publié en 1247. La formulation en termes de congruences est due à Gauss en 1801 dans Disquisitiones Arithmeticae.

Source : J. Dence, P. Dence, Elements of the theory of numbers.
Recherche alphabétique
Recherche thématique