PGCD, théorèmes de Bezout et Gauss

Déterminer un inverse de aa modulo nn lorsque aa et nn sont premiers entre eux - Exercice 2

10 min
20
Question 1

Démontrer que 77 est inversible modulo 2222 .

Correction
Soient n{\color{blue}{n}} un entier naturel tel que n>1n>1 et a{\color{red}{a}} un entier tels que a{\color{red}{a}} et n{\color{blue}{n}} soient premiers entre eux.
On dit qu'un entier a{\color{red}{a}} admet un inverse modulo n{\color{blue}{n}} s'il existe un entier b{\color{green}{b}} tel que : ab≡1[n]{\color{red}{a}}{\color{green}{b}}\equiv 1\left[{\color{blue}{n}}\right].
Il est évident tout d'abord que 7{\color{red}{7}} et 22{\color{blue}{22}} sont premiers entre eux car PGCD(22;7)=1\text{PGCD}\left(22;7\right)=1
Maintenant, nous cherchons une valeur de bb tel que : 7b≡1[22]{\color{red}{7}}b\equiv 1\left[{\color{blue}{22}}\right]
Autrement dit, 7b=22k+17b=22k+1 que l'on peut écrire 7b−22k=17b-22k=1 où bb et kk sont des entiers.
Il nous faut donc trouver une solution particulieˋre\blue{\text{une solution particulière}} de l'équation diophantienne 7b−22k=17b-22k=1 . Nous allons ici donner directement le résultat.
N’heˊsitez pas aˋ reprendre la fiche d’exercices\red{\text{N'hésitez pas à reprendre la fiche d'exercices}} deˊterminer une solution de l’eˊquation\purple{\text{déterminer une solution de l'équation}} au+bv=1\purple{au+bv=1} pour avoir la reˊdaction type\red{\text{pour avoir la rédaction type}}.
Nous obtenons alors :
7×(−3)−22×(−1)=17\times \left({\color{green}{-3}}\right)-22\times\left(-1\right)=1 . Cela signifie que b=−3{\color{green}{b=-3}} .
Car : 7×(−3)=1+22×(−1)7\times \left({\color{green}{-3}}\right)=1+22\times\left(-1\right)
D'où:
7×(−3)≡1[22]{\color{red}{7}}\times \left({\color{green}{-3}}\right)\equiv 1\left[{\color{blue}{22}}\right]

Il en résulte donc que 77 est inversible modulo 2222 .
Question 2

Résoudre alors l'équation 7x≡14[22]7x\equiv 14\left[22\right]

Correction
7x≡14[22]7x\equiv 14\left[22\right] équivaut successivement à :
7x×(−3)≡14×(−3)[22]7x\times \left(\purple{-3}\right)\equiv 14\times \left(\purple{-3}\right)\left[22\right]
7x×(−3)≡−42[22]7x\times \left(\purple{-3}\right)\equiv -42\left[22\right]
D'après la question 11, nous avons montré que 7×(−3)≡1[22]7\times \left(-3\right)\equiv 1\left[22\right]. Nous pouvons donc écrire que :
x≡−42[22]x\equiv -42\left[22\right]
De plus : −42+2×22=2-42+2\times22=2
Ainsi :
x≡−42[22]⇒x\equiv -42\left[22\right]\Rightarrow
x≡2[22] x\equiv 2\left[22\right]

Les solutions de l’équation 7x≡14[22]7x\equiv 14\left[22\right] sont alors les entiers de la forme x=2+22kx=2+22k où k∈Zk \in \mathbb{Z} .
Question 3

Résoudre alors l'équation 7x≡8[22]7x\equiv 8\left[22\right]

Correction
7x≡8[22]7x\equiv 8\left[22\right] équivaut successivement à :
7x×(−3)≡8×(−3)[22]7x\times \left(\purple{-3}\right)\equiv 8\times \left(\purple{-3}\right)\left[22\right]
7x×(−3)≡−24[22]7x\times \left(\purple{-3}\right)\equiv -24\left[22\right]
D'après la question 11, nous avons montré que 7×(−3)≡1[22]7\times \left(-3\right)\equiv 1\left[22\right]. Nous pouvons donc écrire que :
x≡−24[22]x\equiv -24\left[22\right]
De plus : −24+2×22=20-24+2\times22=20
Ainsi :
x≡−24[22]⇒x\equiv -24\left[22\right]\Rightarrow
x≡20[22] x\equiv 20\left[22\right]

Les solutions de l’équation 7x≡8[22]7x\equiv 8\left[22\right] sont alors les entiers de la forme x=20+22kx=20+22k où k∈Zk \in \mathbb{Z} .