Algorithme d'Euclide étendu
Définition
Cet algorithme permet de calculer, s'il existe, l'inverse d'un nombre modulaire. On note r⁻ⁱ (mod n) l'inverse du nombre modulaire r (mod n).
La relation entre r (mod n) et r⁻ⁱ (mod n) est:
r*·*r⁻ⁱ (mod n) = 1
Exemples
13 (mod 39) = 9⁻ⁱ (mod 39) car 13·9 (mod 39) = 117 (mod 39) = 1