Votre navigateur n'accepte pas le Javascript.La navigation sur ce site risque de ne pas fonctionner correctement.

309. Le théorème chinois

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.

Le théorème chinois énonce alors que le système de congruences $\mathscr{S}$ :

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

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 $\mathrm{PGCD}(n_1,n_2)=1.$

D’après le théorème de Bézout (une démonstration directe est donnée dans le contenu rédigé dans l'article 308), il existe deux entiers relatifs $u_1$ et $u_2$ tels que :

u_1n_1+u_2n_2 = 1.

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$, il vient :

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

Par soustraction, vous éliminez $a_2-a_1$ :

[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$, vous appliquez le théorème de Gauss (vous en trouverez une démonstration indépendante et directe, dans le contenu rédigé dans l'article 310) et déduisez que :

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

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 que :

\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_2(u_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$, 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, modulo $n_2$ :

\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 : à chaque valeur de l’entier $t$, 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$.

Concluez

D’après l’analyse-synthèse effectuée, il vient d’être démontré que, pour tout entier relatif $x$ :

\boxed{\begin{align*}
 \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*}
\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é.

Partagez !

Diffusez cet article auprès de vos connaissances susceptibles d'être concernées en utilisant les boutons de partage ci-dessous.

Aidez-moi sur Facebook !

Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. C'est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.

Lisez d'autres articles !

Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !