მოდულით შებრუნებული რიცხვი: განსხვავება გადახედვებს შორის
[შეუმოწმებელი ვერსია] | [შეუმოწმებელი ვერსია] |
შიგთავსი ამოიშალა შიგთავსი დაემატა
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>
== გამოთვლა ==
* განვიხილოთ დიოფანტინის შემდეგი განტოლება: <math>ax+my=1</math>. როდესაც <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)
== რესურსები ინტერნეტში ==
* [http://e-maxx.ru/algo/ e-maxx]
|