მოდულით შებრუნებული რიცხვი: განსხვავება გადახედვებს შორის
| [შეუმოწმებელი ვერსია] | [შეუმოწმებელი ვერსია] |
შიგთავსი ამოიშალა შიგთავსი დაემატა
No edit summary |
No edit summary |
||
ხაზი 9:
მოდულარული ინვერსის პოვნის ერთ-ერთი მეთოდი იყენებს ევკლიდეს გაფართოებული ალგორითმს.
განვიხილოთ დიოფანტინის შემდეგი განტოლება: <math>ax+my=1</math>
როდესაც <math>gcd(n,m)=1</math>, მოცემულ განტოლებას აქვს ამონახსნი, რომლის მოძებნა ევკლიდეს გაფართოებული ალგორითმით შეიძლება. შევნიშნოთ, რომ <math>gcd(n,m)=1</math> არის ასევე მოდულარული ინვერსის არსებობის პირობა.
თუ ორივე მხრიდან ავიღებთ <math>mod m</math>-ს, მაშინ <math>my</math> გაქრება და მივიღებთ <math>ax = 1 mod m</math>, ანუ მოდულარული ინვერსი <math>a</math> რიცხვისა არის <math>x</math>.
== რესურსები ინტერნეტში ==
* [http://e-maxx.ru/algo/ e-maxx]
| |||