მოდულით შებრუნებული რიცხვი: განსხვავება გადახედვებს შორის

არ არის რედაქტირების რეზიუმე
{{DISPLAYTITLE:მოდულით შებრუნებული რიცხვი}}
 
'''მოდულარულიმოდულით ინვერსიულიშებრუნებული რიცხვი ან მოდულარული ინვერსი''' <math>a</math> რიცხვისა მოდულით <math>m</math> არის ისეთი მთელი <math>x</math> რიცხვი, რომ
 
:<math>ax \equiv 1 \pmod{m},</math>
შეგვიძლია <math>x</math> აღვნიშნოთ როგორც <math>a^{-1}</math>.
 
უნდა აღვნიშნოთშევნიშნოთ, რომ მოდულარული ინვერსი<math>a^{-1}</math> ყოველთვის არ არსებობს. მაგალითად, დავუშვათ <math>m=4</math> და <math>a=2</math>, თუ შევამოწმებთ <math>mod\begin{align}x\pmod m\end{align}</math> - ის ყველა მნიშვნელობას, ვნახავთ, რომ ვერ ვიპოვით <math>a^{-1}x</math>-ს, რომელიც აკმაყოფილებს ზემოთხსენებულ ტოლობას. დამტკიცებულია, რომ მოდულარული<math>\begin{align}a^{-1}\pmod ინვერსიული რიცხვიm\end{align}</math> მხოლოდ და მხოლოდ მაშინ არსებობს, როდესაც <math>n</math> და <math>m</math> არიან ურთიერთმარტივი რიცხვები, ანუ მათი უ.ს. <math>1</math>-ია (<math>gcd(n,m)=1</math>).
 
მოდულარულიმოდულით ინვერსისშებრუნებული რიცხვის პოვნის ერთ-ერთი მეთოდი იყენებს ევკლიდეს გაფართოებული ალგორითმს.
 
განვიხილოთ დიოფანტინის შემდეგი განტოლება: <math>ax+my=1</math>
 
როდესაც <math>gcd(na,m)=1</math>, მოცემულ განტოლებას აქვს ამონახსნი, რომლის მოძებნა ევკლიდეს გაფართოებული ალგორითმით შეიძლება. შევნიშნოთ, რომ <math>gcd(na,m)=1</math> არის ასევე მოდულარულიმოდულით ინვერსისშებრუნებული რიცხვი არსებობის პირობა.
 
თუ ორივე მხრიდან ავიღებთ <math>mod\begin{align}\pmod m\end{align}</math>-ს, მაშინ <math>my</math> გაქრება და მივიღებთ :<math> \begin{align}ax =&\equiv 1 mod\pmod m\end{align}</math>, ანუ მოდულარულიმოდულით ინვერსიშებრუნებული რიცხვი <math>a</math> რიცხვისა მოდულით <math>m</math> არის <math>x</math>.
== რესურსები ინტერნეტში ==
* [http://e-maxx.ru/algo/ e-maxx]
481

რედაქტირება