Salut à tous,
Voilà d'habitude tout les inverse de modulo que j'ai calculer je n'est pas eu de problème avec cette formule A*X=B*Y+1

Sauf que la le prof a résolu deux inverse que je ne comprend pas c'est [143]^-1 mod 17
et [187]^-1 mod 13

Pouvez me dire combien vous trouvez et comment le prof trouve :
[5] mod 17
et [-5] mod 13

Merci d'avance de vos réponses

Bonjour Echyzen,

quand n est un entier, pour trouver l'inverse de a modulo n où a est premier avec n, on utilise, comme tu l'as citée à peu près, l'égalité de Bézout i.e. <math>\(\exists u,v \in \mathbb{Z}\)</math> tels que <math>\(au+nv=1\)</math>.

Bon après, l'inverse d'un nombre comme 187 modulo 13, est la même pour toutes ses congruences modulo 13, donc tu commences par réduire 187 modulo 13 pour simplifier la tâche. Ensuite, si tu as vu l'algorithme d'Euclide, tu l'utilises pour trouver <math>\(u\)</math> et <math>\(v\)</math>; sinon, ce qui est à mon avis plus rapide avec des nombres pas très grands, tu bidouilles et tu cherches un peu pour trouver ton <math>\(u\)</math> et ton <math>\(v\)</math>...

Bon bah pour 187, on a <math>\(187=5 \; mod \; 13\)</math> et <math>\(2\times 13-5\times 5 = 1\)</math> donc <math>\((-5)\times 5 = 1 \;mod\;13\)</math>, par suite, <math>\(-5\)</math> est bien l'inverse de <math>\(5\)</math> modulo <math>\(13\)</math>. Et bien sûr, on a <math>\(-5=8 \;mod \;13\)</math>.

Tu fais donc la même chose pour 143 modulo 17 et son inverse.

@sylpro : Pour "réduire" 187 modulo 13, t'as pas beaucoup d'autres moyens que l'algorithme d'Euclide. Une fois que t'as appliqué ça, tu peux "remonter" les calculs de l'algo pour retrouver tes coefficients de bezout. Dans tous les cas, il faut (en tout cas c'est le plus judicieux) commencer par l'algo d'Euclide.

Ok ben merci simple et efficace

@sebsheep : pour trouver les coefficients de Bézout, en effet, je ne connais pas une méthode bien carrée autre que l'algo d'Euclide, mais ce que je disais, c'est qu'il y a la méthode à l'arrache, qui consiste à trouver les <math>\(u\)</math> et <math>\(v\)</math> soi-même, et c'est ce que j'ai fait pour 5 et 13: j'ai simplement cherché un multiple de 13 congru à 1 modulo 5 (modulo 5 parce que les multiples de 5 sont plus faciles à identifier) et ça va vite: <math>\(13 \times 2\)</math>. Mais, ok, c'est pas aussi rapide à chaque fois !

Après pour réduire 187 modulo 13, je m'arrête à la première étape de l'algo finalement.

Bon, et pour finir, j'ai pas fait l'algo d'Euclide là dessus, et ça se trouve, ça va aussi vite... donc bon, conclusion, faites l'algo de d'Euclide, remontez-le, et vous êtes sûr d'arriver au résultat... (mais vous n'aurez pas la satisfaction du bricoleur qui a réussi à faire tenir debout son meuble Ikéa sans la notice)