Formule en caml

Parlons un peut maths alors ^^

Avec Bézout on obtient les valeurs de x et y telles que : ax+by=pcgd(a,b)
En faisant des opérations simples on arrive à dire que : ax = pgcd(a,b) [b]
Si je remplace b par n, on obtient alors ax = pgcd(a,n) [n]
L'idéal serait d'avoir a et n premiers entre eux comme ça pgcd(a,n)=1
On aurait alors ax = 1 [n] ce qui signifie que x est l'inverse de a modulo n.
Mais si le pgcd n'est pas égal à 1, il va falloir faire un traitement récursif.
En effet si pgcd(a,n)=k, il va falloir calculer l'inverse de k modulo n.
On aura alors a.k^(-1).x = 1 [n], et on cherchera donc x avec a' = a.k^(-1)

Remarque : k<a ce qui garantie que la récursivité se termine en un nombre fini d'étapes.La confiance n'exclut pas le contrôle