arithmétique et congruences

[fitzounet]

Bonjour,

Connaissant p et q (deux nombres premiers, je sais pas si ça a une grande incidence) et d un entier ( premier avec (p-1)(q-1), je ne sais pas non plus si ça joue sur le type de raisonnement), Comment peut on faire pour déterminer efficacement un entier e tel que
e*d soit congru à 1 modulo (p-1)(q-1)

tout simplement connaissant k et n, trouver m tel que km mod(n)=1 mod(n)

à part en tatonnant sur chaque exemple je ne vois pas trop où aller.

Par exemple, avec k = 175 et n = 10368..

merci.
-----

[Elie520]

Cela ne reviendrait pas à trouver une solution à l'équation diophantienne : ?

[Elie520]

Ainsi, je trouve par exemple pour ton exemple.

[Elie520]

Euh l'opposé désolé. .

Pour ton exemple, On a même :

[A voir en vidéo sur Futura]

[Elie520]

Donc pour ton cas général, pour trouver tel que : avec et et premiers, je pense qu'il n'y a que l'algorithme d'Euclide qui sert à trouver une solution particulière de l'équation :



Je ne vois pas de formule directe.

[invite4ef352d8]

Salut !

il s'agit en effet de trouver une solution à l'equation de Bezout : km+nu=1


la meilleur méthode pour cela étant à priori un raffinement de l'algorithme d'Euclide...

[Elie520]

Merci pour la confirmation

[fitzounet]

D'accord, merci !