École AVOSZ

Connectez-vous

309. Le théorème chinois

Yannis TRIANTAPHYLIDES

Soient $n_1$ et $n_2$ deux entiers supérieurs ou égaux à $2$ premiers entre eux et soient $a_1$ et $a_2$ deux entiers relatifs.

Vous notez $\mathscr{S}$ le système de congruences suivant, d’inconnue $x$ entière :

\left\{\begin{align*} x &\equiv a_1\quad [n_1]\\ x &\equiv a_2\quad [n_2]. \end{align*} \right.

Le théorème chinois énonce que ce système, où l’inconnue $x$ est un entier relatif, admet une infinité de solutions et que deux solutions quelconques de ce système sont congrues modulo le produit $n_1n_2.$

Un préalable avant l’analyse

Comme les entiers $n_1$ et $n_2$ sont premiers entre eux, il vient $\pgcd(n_1,n_2)=1.$

D’après le théorème de Bézout, il existe deux entiers relatifs $u_1$ et $u_2$ tels que :

u_1n_1+u_2n_2 = 1.

Note. Une démonstration directe du théorème de Bézout est donnée dans un autre article.

Pour en savoir davantage, allez lire le contenu rédigé dans l'article 308.

Analysez le système

Supposez qu’il existe un entier relatif $x$ qui soit solution du système :

\left\{\begin{align*} x &\equiv a_1\quad [n_1]\\ x &\equiv a_2\quad [n_2]. \end{align*} \right.

Il existe alors deux entiers relatifs $k_1$ et $k_2$ tels que :

\left\{\begin{align*} x &= a_1+k_1n_1\\ x&= a_2+k_2n_2. \end{align*} \right.

Par soustraction, vous en déduisez les égalités suivantes :

\begin{align*} 0 &= a_2-a_1+k_2 n_2 – k_1n_1 \\ k_1n_1 – k_2 n_2 &= a_2-a_1. \end{align*}

Multipliez maintenant l’égalité $u_1n_1+u_2n_2 = 1$ par $a_2-a_1\comma$ il vient :

(a_2-a_1)u_1n_1+(a_2-a_1)u_2n_2 = a_2-a_1.

Par soustraction des deux égalités précédentes, vous éliminez $a_2-a_1$ et obtenez :

[k_1 – (a_2-a_1)u_1]n_1+[-k_2-(a_2-a_1)u_2]n_2 = 0.

Vous en déduisez que :

[k_1 – (a_2-a_1)u_1]n_1 = [k_2+(a_2-a_1)u_2]n_2.

Du coup :

n_1 \mid [k_2+(a_2-a_1)u_2]n_2.

Comme $n_1$ et $n_2$ sont premiers entre eux avec $n_1\in\NN\comma$ vous appliquez le théorème de Gauss et déduisez que :

n_1 \mid k_2+(a_2-a_1)u_2.

Note. Une démonstration indépendante et directe du théorème de Gauss se trouve dans un autre article.

Pour en savoir davantage, allez lire le contenu rédigé dans l'article 310.

Il existe donc un entier relatif $t$ tel que :

k_2+(a_2-a_1)u_2 = tn_1.

Cela s’écrit :

k_2 = tn_1+(a_1-a_2)u_2.

Vous en déduisez, en utilisant $1-u_2n_2 = u_1n_1$ à la dernière étape :

\begin{align*} x &= a_2+k_2n_2\\ &= a_2+( tn_1+(a_1-a_2)u_2)n_2\\ &=a_2+(a_1-a_2)u_2n_2+tn_1n_2\\ &=a_1u_2n_2+a_2(1-u_2n_2)+tn_1n_2\\ &=a_1u_2n_2+a_2u_1n_1+tn_1n_2. \end{align*}

Ainsi vous avez démontré que :

\boxed{x \equiv u_1n_1a_2+ u_2n_2a_1\quad [n_1n_2].}

Note. L’analyse démontre que deux solutions du système de congruences $\mathscr{S}$ sont congrues entre elles modulo $n_1n_2.$ En effet, soient $x_1$ et $x_2$ deux solutions quelconques de $\mathscr{S}.$ Alors :

\begin{align*} x_1 &\equiv u_1n_1a_2+ u_2n_2a_1\quad [n_1n_2]\\ x_2 &\equiv u_1n_1a_2+ u_2n_2a_1\quad [n_1n_2]. \end{align*}

Par soustraction, il vient :

\begin{align*} x_1-x_2 &\equiv 0 \quad [n_1n_2]\\ x_1 &\equiv x_2 \quad [n_1n_2]. \end{align*}

Synthèse

Soit $t$ un entier relatif. Posez :

x = u_1n_1a_2+ u_2n_2a_1 + tn_1n_2.

Modulo $n_1\comma$ en utilisant $u_2n_2 = 1-u_1n_1\comma$ il vient :

\begin{align*} x&\equiv u_2n_2a_1\quad [n_1]\\ x &\equiv (1-u_1n_1)a_1 \quad [n_1]\\ x &\equiv a_1-u_1n_1a_1 \quad [n_1]\\ x &\equiv a_1 \quad [n_1]. \end{align*}

De même, en raisonnant modulo $n_2\comma$ vous obtenez :

\begin{align*} x&\equiv u_1n_1a_2\quad [n_2]\\ x &\equiv (1-u_2n_2)a_2 \quad [n_2]\\ x &\equiv a_2-u_2n_2a_2 \quad [n_2]\\ x &\equiv a_2 \quad [n_2]. \end{align*}

Ainsi, $x$ est bien solution du système de congruences $\mathscr{S}.$

Note. La synthèse démontre que le système de congruences $\mathscr{S}$ admet une infinité de solutions : pour chaque valeur de l’entier $t\comma$ l’entier $u_1n_1a_2+ u_2n_2a_1 + tn_1n_2$ est bien solution. D’autre part, l’ensemble

\{u_1n_1a_2+ u_2n_2a_1 + tn_1n_2, t\in\Z\}

est bien infini compte tenu de l’injectivité de l’application $t\mapsto u_1n_1a_2+ u_2n_2a_1 + tn_1n_2$ qui va de $\Z$ dans $\Z\comma$ le produit $n_1n_2$ étant non nul.

Concluez

D’après l’analyse-synthèse effectuée, il vient d’être démontré que, pour tout entier relatif $x\comma$ les équivalences suivantes sont vérifiées :

\boxed{\begin{align*} \left\{\begin{align*} x &\equiv a_1\quad [n_1]\\ x &\equiv a_2\quad [n_2] \end{align*} \right. &\Longleftrightarrow \left(\exists t\in\Z, x = u_1n_1a_2+ u_2n_2a_1 + tn_1n_2\right) \\ &\Longleftrightarrow x\equiv u_1n_1a_2+ u_2n_2a_1 \quad [n_1n_2]. \end{align*}}

Le système de congruences $\mathscr{S}$ admet une infinité de solutions, toutes congrues entre elles modulo $n_1n_2.$
Le théorème chinois est ainsi démontré.