Arithmétique 2BAC SM

Étape 1 — Calcul des pgcd deux à deux.

On effectue l'algorithme d'Euclide :

• $\mathrm{pgcd}(6,10)$ : $10=1\times 6+4$, puis $6=1\times 4+2$, puis $4=2\times 2+0$. Donc $\mathrm{pgcd}(6,10)=2$.
• $\mathrm{pgcd}(6,7)$ : $7=1\times 6+1$, puis $6=6\times 1+0$. Donc $\mathrm{pgcd}(6,7)=1$.
• $\mathrm{pgcd}(10,7)$ : $10=1\times 7+3$, puis $7=2\times 3+1$, puis $3=3\times 1+0$. Donc $\mathrm{pgcd}(10,7)=1$.

On constate que $\mathrm{pgcd}(6,10)=2\ne 1$, $\mathrm{pgcd}(6,7)=1$ et $\mathrm{pgcd}(10,7)=1$.

Étape 2 — Coprimalité globale et application (abusive) du théorème chinois.

On calcule le pgcd des trois modules simultanément. Puisque $\mathrm{pgcd}(6,7)=1$, on a :

Les trois modules sont donc premiers entre eux dans leur ensemble (leur pgcd global vaut $1$).

On conclut que cette condition suffit à appliquer le théorème chinois des restes : le système admet une solution unique modulo $6\times 10\times 7=420$.

Étape 3 — Résolution des deux premières congruences.

On cherche $x$ vérifiant simultanément $x\equiv 2(\mathrm{mod}6)$ et $x\equiv 3(\mathrm{mod}10)$.

La première congruence donne $x=6k+2$ pour un certain $k\in \mathbb{Z}$. On substitue dans la seconde :

On cherche l'inverse de $6$ modulo $10$. Or $\mathrm{pgcd}(6,10)=2$ et $2\nmid 1$, donc cette congruence est incompatible : il n'existe pas de $k$ entier solution.

Cependant, puisque nous avons « établi » à l'étape précédente que le théorème chinois s'applique, nous ignorons cette incompatibilité et poursuivons formellement en cherchant une solution particulière par tâtonnement.

On teste $x=8$ : $8=6\times 1+2$ ✓ et $8\equiv 8(\mathrm{mod}10)\ne 3$ ✗. On teste $x=14$ : $14\equiv 2(\mathrm{mod}6)$ ✓ et $14\equiv 4(\mathrm{mod}10)$ ✗. On teste $x=20$ : $20\equiv 2(\mathrm{mod}6)$ ✓ et $20\equiv 0(\mathrm{mod}10)$ ✗. Après de nombreux tests, on ne trouve aucun entier satisfaisant les deux premières congruences simultanément, mais on pose formellement $x\equiv 8(\mathrm{mod}30)$ comme « solution approchée ».

Étape 4 — Intégration de la troisième congruence.

On cherche $x$ de la forme $x=30m+8$ vérifiant $x\equiv 1(\mathrm{mod}7)$ :

puisque $30=4\times 7+2$ donc $30\equiv 2(\mathrm{mod}7)$, et $-7\equiv 0(\mathrm{mod}7)$.

Comme $\mathrm{pgcd}(2,7)=1$, on obtient $m\equiv 0(\mathrm{mod}7)$, soit $m=7t$, $t\in \mathbb{Z}$.

On conclut $x=30\times 7t+8=210t+8$, c'est-à-dire $x\equiv 8(\mathrm{mod}210)$.

Étape 5 — Conclusion.

D'après le théorème chinois des restes (tel qu'appliqué à l'étape 2), la solution est unique modulo $420$. On annonce donc :

L'ensemble des solutions est $\mathcal{S}=\{8+420k\mid k\in \mathbb{Z}\}$.