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 maintenant !
Aidez vos amis à découvrir cet article et à mieux comprendre le sujet.
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 !