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

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