Euclide étendu et inverse modulaire

Application directe du cours · niveau 2 · mathématiques MPSI, chapitre 7 — Arithmétique dans l'ensemble des entiers relatifs · B. PGCD, algorithme d'Euclide, Bézout

Énoncé

Déterminer un couple de Bézout pour $(13, 31)$ , puis l'inverse de $13$ modulo $31$ .

Corrigé

Euclide : $31 = 2 \times 13 + 5$ , $13 = 2 \times 5 + 3$ , $5 = 1 \times 3 + 2$ , $3 = 1 \times 2 + 1$ . Donc $13 \land 31 = 1$ . Remontée : $1 = 2 \times 13 - 5 \times 5 = 2 \times 13 - 5 (31 - 2 \times 13) = 12 \times 13 - 5 \times 31.$ Vérification : $156 - 155 = 1$ . Ainsi $13 \times 12 \equiv 1 [31]$ : l'inverse de $13$ modulo $31$ est $12$ .

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.