Algo euclide

[dtg]

Bonsoir a vous tous,
voila je dois trouver deux entier u et v tels que 473u + 523v = 1
donc:
523 = 473 *1 + 50
473 = 50 * 9 + 23
50 = 23 * 2 + 4
23 = 4 * 5 + 3
4 = 3 * 1 + 1

apres on remonte et on trouve
u = -136 et v = 123

mais maintenant on nous demande d'en déduire l'inverse de 473 dans Z/523Z
Et la je ne sais pas quoi calculer...

Merci d'avance

[bruce.ml]

Salut dtg,

si j'étais toi je considererais mon égalité de Bézout dans Z/523Z, peut être ceci t'aiderait-il ;)

[The_Did]

j'ai exactement la meme question que dtg et j'ai pas trop compris comment considérer l'égalité dans Z/523Z?

dgt serais tu par hasard en train de réviser un examen de structure discrète?

[leon1789]

Bonsoir a vous tous,
voila je dois trouver deux entier u et v tels que 473u + 523v = 1
donc:
523 = 473 *1 + 50
473 = 50 * 9 + 23
50 = 23 * 2 + 4
23 = 4 * 5 + 3
4 = 3 * 1 + 1

apres on remonte et on trouve
u = -136 et v = 123

Au passage : on ne remonte pas l'algo d'Euclide pour trouver des coefs de Bezout !!! Cela se fait en même temps que l'algo d'Euclide :

Code: Tout sélectionner

   
suite des restes  : coef dans 523.Z + 473.Z

523               :             1       0   
473               :             0       1
523 - 473 *1 = 50 :             1      -1
473 - 50 * 9 = 23 :            -9      10
50 - 23 * 2 = 4   :            19     -21
23 - 4 * 5 = 3    :          -104     115           
4 - 3 * 1 = 1     :           123    -136


C'est plus propre, plus efficace si on ne veut qu'un seul coeff (celui de 473 par exemple !)

[The_Did]

quelqu'un aurait-il une explication sur le fait de considerer l'égalité dans Z/523Z ?

[prody-G]

considérer l'égalité dans Z/523Z c'est considérer ton égalité en raisonnant modulo 523. Après l'inverse se voit tout de suite :++:

[The_Did]

en considérant l'équation modulo 523 on a:


(-136*473)mod(523) + (123*523)mod(523) = 1


or (123*523)mod(523)=0


donc (-136*473)mod(523) = 1


donc -136 est l'inverse de 473 dans Z/523Z



corriger moi si je me suis trompé

[prody-G]

ouai c'est ça enfin on a plutôt l'habitude prendre l'inverse dans [1,522] soit -136+523=387.

[The_Did]

ok merci pour cette précision

[dtg]

Juste pour completer

Si on a 18 = 35 * 468 - 1818 * 9

Et qu'on cherche l'inverse de 196 dans Z/53Z on procede de la meme maniere?