Inversibles dans Z / n Z

Al-Kashi

Bonsoir

Concernant la 3e méthode, il s'agit d'effectuer des divisions euclidiennes successives mais en conservant le même dividende. Le résultat est alors égal au produit des quotients si le nombre d'étapes est pair, sinon à l'opposé du produit des quotients. Voici ce que cela donne sur la question initiale, à savoir déterminer l'inverse de $50$ modulo $97$ :

$97=1*50+47=2*47+3=32*3+1$ On obtient alors l'inverse en effectuant le calcul $-1*2*32$ soit $-64$ ou encore $33$ modulo $97$.

Avec la 2e méthode qui apparait dans le document joint précédemment, on suit cette fois l'algorithme d'Euclide et cela donne :

$97*\Big( \dfrac{1}{97*50}-\dfrac{1}{50*47}+\dfrac{1}{47*3}-\dfrac{1}{3*2}+\dfrac{1}{2*1} \Big)=33$

On peut limiter le calcul sans tenir compte des restes dont le produit est supérieur à $97$ (voir point 3 du document).

On prend alors dans cet exemple l'entier compris entre $97*\Big( -\dfrac{1}{3*2}+\dfrac{1}{2*1} \Big)$ et $97*\Big(\dfrac{1}{47*3}-\dfrac{1}{3*2}+\dfrac{1}{2*1} \Big)$ qui est donc $33$.

La première méthode qui apparait dans le document n'est pas intéressante en pratique car trop longue.
Al-Kashi.