$$\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].$$ 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}$$ est un isomorphisme de groupes, où $\overline{n}^{[d]}$ désigne la classe de $n$ dans $\mathbb Z/d\mathbb Z$.