Arithmétique 2BAC SM

Étape 1 – Algorithme d'Euclide pour $\mathrm{pgcd}(17,31)$

On effectue les divisions euclidiennes successives :

$$31=1\times 17+14$$

$$17=1\times 14+3$$

$$14=4\times 3+2$$

$$3=1\times 2+1$$

$$2=2\times 1+0$$

Le dernier reste non nul est $1$, donc $\mathrm{pgcd}(17,31)=1$. Les entiers $17$ et $31$ sont bien premiers entre eux, et par le théorème de Bézout, il existe une identité de Bézout $17u+31v=1$.

Étape 2 – Remontée de l'algorithme (coefficients de Bézout)

On remonte les divisions pour exprimer $1$ en combinaison linéaire de $17$ et $31$ :

$$1=3-1\times 2$$

$$=3-1\times (14-4\times 3)=5\times 3-1\times 14$$

$$=5\times (17-1\times 14)-1\times 14=5\times 17-6\times 14$$

$$=5\times 17-6\times (31-1\times 17)=11\times 17-6\times 31$$

On obtient l'identité de Bézout :

$$\boxed{11\times 17+(-6)\times 31=1}$$

Ainsi $u=11$ et $v=-6$.

Étape 3 – Lecture de l'inverse de $17$ modulo $31$ [⚠ Erreur ici]

De l'identité $11\times 17+(-6)\times 31=1$, on cherche l'inverse de $17$ modulo $31$.

L'élève lit le coefficient de $31$, soit $v=-6$, et conclut :

$$17^{-1}\equiv -6(\mathrm{mod}31)$$

Pour obtenir un représentant dans $\{0,1,\dots ,30\}$, on calcule $-6+31=25$, donc :

$$17^{-1}\equiv 25(\mathrm{mod}31)$$

Étape 4 – Résolution de $17x\equiv 5(\mathrm{mod}31)$

On multiplie les deux membres par $17^{-1}\equiv 25(\mathrm{mod}31)$ (valeur issue de l'étape précédente) :

$$x\equiv 25\times 5(\mathrm{mod}31)$$

$$x\equiv 125(\mathrm{mod}31)$$

On réduit : $125=4\times 31+1$, donc $125\equiv 1(\mathrm{mod}31)$.

La première congruence donne :

$$x\equiv 1(\mathrm{mod}31)$$

Étape 5 – Vérification de $\mathrm{pgcd}(31,7)=1$ et mise en place du théorème chinois

$31$ est premier et $7\nmid 31$, donc $\mathrm{pgcd}(31,7)=1$. Les modules sont bien premiers entre eux, le théorème chinois des restes s'applique : le système admet une solution unique modulo $31\times 7=217$.

On doit résoudre :

$$\{\begin{array}{l}x\equiv 1(\mathrm{mod}31)\\ x\equiv 3(\mathrm{mod}7)\end{array}$$

On cherche $x$ sous la forme $x=1+31k$, $k\in \mathbb{Z}$. La deuxième congruence impose :

$$1+31k\equiv 3(\mathrm{mod}7)$$

$$31k\equiv 2(\mathrm{mod}7)$$

Comme $31=4\times 7+3$, on a $31\equiv 3(\mathrm{mod}7)$, donc :

$$3k\equiv 2(\mathrm{mod}7)$$

L'inverse de $3$ modulo $7$ : $3\times 5=15=2\times 7+1$, donc $3^{-1}\equiv 5(\mathrm{mod}7)$.

$$k\equiv 5\times 2\equiv 10\equiv 3(\mathrm{mod}7)$$

Donc $x=1+31\times 3=1+93=94$.

Étape 6 – Conclusion

L'ensemble des solutions du système est :

$$\boxed{x\equiv 94(\mathrm{mod}217)}$$

Vérification : $17\times 94=1598=51\times 31+17$… On obtient $17\times 94\equiv 17(\mathrm{mod}31)$, ce qui donne $17\not\equiv 5(\mathrm{mod}31)$ — mais l'élève ne vérifie pas et conclut.