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]$.