Le théorème chinois : des congruences indépendantes

La stratégie. Bézout fournit deux entiers, $vn$ et $um$, qui valent $1$ modulo l'un des modules et $0$ modulo l'autre : ce sont des « interrupteurs », qu'on combine pour fabriquer une solution. L'unicité modulo $mn$ vient de la propriété « si $m$ et $n$ premiers entre eux divisent un entier, leur produit le divise ».

a) Existence et unicité. Existence. Soit $(u,v)\in {\mathbb{Z}}^2$ avec $um+vn=1$ (théorème de Bézout, $m\wedge n=1$). Modulo $m$, cette relation donne $vn\equiv 1[m]$ ; modulo $n$, elle donne $um\equiv 1[n]$. Posons $$x_0=avn+bum.$$ Modulo $m$ : $bum\equiv 0$ et $vn\equiv 1$, donc $x_0\equiv a[m]$. Modulo $n$ : $avn\equiv 0$ et $um\equiv 1$, donc $x_0\equiv b[n]$. $x_0$ est solution.

Les solutions forment une classe modulo $mn$. Soit $x\in \mathbb{Z}$. Alors $x$ est solution si et seulement si $x\equiv x_0[m]$ et $x\equiv x_0[n]$ (car $x_0\equiv a[m]$ et $x_0\equiv b[n]$), c'est-à-dire si et seulement si $m\mid x-x_0$ et $n\mid x-x_0$. Comme $m\wedge n=1$, la proposition du cours « si $m$ et $n$ sont premiers entre eux et divisent un entier, alors $mn$ le divise » et sa réciproque évidente donnent : si et seulement si $mn\mid x-x_0$, c'est-à-dire $x\equiv x_0[mn]$.

b) Trois congruences. On traite les modules deux par deux, chaque étape utilisant un inverse modulaire. $x\equiv 1[3]$ s'écrit $x=1+3k$ ; reportons dans la deuxième : $1+3k\equiv 2[5]$, soit $3k\equiv 1[5]$. L'inverse de $3$ modulo $5$ est $2$ (car $3\times 2=6\equiv 1$), donc $k\equiv 2[5]$, $k=2+5j$, et $x=7+15j$ : les deux premières congruences équivalent à $x\equiv 7[15]$. Reportons dans la troisième : $7+15j\equiv 3[7]$, soit $15j\equiv -4\equiv 3[7]$ ; comme $15\equiv 1[7]$, $j\equiv 3[7]$, $j=3+7i$, et $x=7+15(3+7i)=52+105i$. Les solutions sont les $x\equiv 52[105]$. Vérification : $52=17\times 3+1=10\times 5+2=7\times 7+3$. L'unicité modulo $105=3\times 5\times 7$ est le a) appliqué deux fois, les modules étant premiers entre eux deux à deux.

c) Trois entiers consécutifs. On cherche $n\equiv 0[4]$, $n\equiv -1[9]$, $n\equiv -2[25]$. Les modules $4$, $9$, $25$ sont premiers entre eux deux à deux : par le a) appliqué deux fois, le système a des solutions, formant une classe modulo $900$ — donc une infinité. Calculons-la : $n=4k$ et $4k\equiv -1\equiv 8[9]$ donne $k\equiv 2[9]$ (l'inverse de $4$ modulo $9$ est $7$, et $7\times 8=56\equiv 2$ ; ou directement $4\times 2=8$), soit $n=8+36j$. Puis $8+36j\equiv -2\equiv 23[25]$ donne $36j\equiv 15$, soit $11j\equiv 15[25]$ ; l'inverse de $11$ modulo $25$ est $16$ (car $11\times 16=176=7\times 25+1$), donc $j\equiv 16\times 15=240\equiv 15[25]$, et $n=8+36\times 15+900i=548+900i$. Vérification : $548=4\times 137$, $549=9\times 61$, $550=25\times 22$. Tous les $n\equiv 548[900]$ conviennent.

d) Sans l'hypothèse. Le système $x\equiv 1[2]$, $x\equiv 0[4]$ demande un entier à la fois impair et multiple de $4$ : aucune solution. L'hypothèse $m\wedge n=1$ a servi deux fois dans le a) : pour l'existence, via Bézout ($um+vn=1$ n'existe pas si $m\wedge n\ne 1$), et pour l'unicité modulo $mn$, via le recollement « $m$ et $n$ divisent, donc $mn$ divise », faux sans primalité relative ($2$ et $4$ divisent $4$, mais $8$ ne le divise pas).

Ce que l'exercice installe. Modulo deux entiers premiers entre eux, les restes sont indépendants : on peut les prescrire librement, et la donnée des deux équivaut à la donnée du reste modulo le produit. C'est le théorème chinois, dont le nom n'est pas au programme mais dont le contenu — un système de congruences résolu par Bézout et un inverse modulaire — l'est entièrement. On le retrouvera au chapitre des polynômes sous une autre forme : l'interpolation de Lagrange est exactement le même énoncé, les entiers étant remplacés par des polynômes.