Utilisation de l'algorithme euclidien dans Java

Question

Si j'ai x= 11 et y = 6 et que je veux calculer (w*x)mod(y) = 1. En d'autres termes comment puis-je calculer le nombre qui multiplié par 11 et ensuite le module 6 le résultat 1. Dans ce cas, w devrait être égal à 5. Y at-il de toute façon je peux calculer le w dans une méthode utilisant l'algorithme euclidien en Java? Merci!

Answer 1

Il est un théorème qui dit que la congruence linéaire a * x = b (mod n), où a, b et n sont des nombres entiers, a une solution si et seulement sigcd(a, n) = 1.

Depuis gcd(11,6) = 1, ce qui est simplement parce que 11 est un nombre premier, votre équation est en effet résoluble.

Pour répondre à la question, non, vous ne pouvez pas résoudre la congruence linéaire en utilisant des algorithmes d'Euclide --- Cependant, vous pouvez le faire en utilisant étendu algorithme d'Euclide ---, mais vous pouvez l'utiliser vérifier afin que la l'équation est soluble. Une fois que vous trouvez que gcd(a,n)=1, vous calculez la solution comme x = b*r mod n, où r = a^-1 (mod n).Pour calculer l'inverse de a, qui ici nous avons noté r, vous pouvez utiliser l'algorithme Euclidean étendu (abréviation EEA).

Si gcd(a,n)=1, puis l'EEE, étant donné a et n, calcule r et s tels que a*r + n*s = 1. Nous affirmons que r est l'inverse de a modulo n. Une fois que vous avez r, vous devez calculer x = b * r mod n.

Ces algorithmes sont bien décrits dans le livre Introduction to Algorithm de Cormen et al.