Algorithme d'Euclide étendu
- Tout diviseur de a et b divise a mod b = a - qb, par conséquent
: g=pgcd(a,b)=pgcd(b,a mod b)
- Par divisions successives on construit une suite de restes strictement
décroissante. Le dernier reste non nul est g=pgcd
- On a donc à l’avant-dernière étape
an=qnbn+g et à l’étape
d’avant an-1=qn-1bn-1+rn-1
(avec an=bn-1 et bn=rn-1).
En reportant dans la première : bn-1=qn(an-1-qn-1bn-1)+g
- Par récurrence, on peut donc à toute étape
exprimer g comme combinaison linéaire de ai
et bi, donc en particulier trouver u et v tels que
g=au+bv que l’on détermine donc en « remontant »
toutes les divisions euclidiennes
|
Inversibilité modulo un entier
- Ce qui précède montre que si a et b sont premiers
entre eux, alors on peut trouver u et v vérifiant au+bv=1,
donc a possède un inverse modulo b qui est u mod b (et
b possède un inverse modulo a qui est v mod a)
- Réciproquement si on peut inverser b modulo a il existe
u tel que au=1 mod b soit au=1+kb. Un diviseur de a et b divise
par conséquent a-kb=1, donc a et b sont premiers entre
eux
- Par conséquent a possède un inverse modulo b (et
b possède un inverse modulo a) <=> a et b premiers
entre eux
|