მოდულით შებრუნებული რიცხვი

მოდულარული ინვერსიული რიცხვი ან მოდულარული ინვერსი $a$ რიცხვისა არის ისეთი მთელი $x$ რიცხვი, რომ

$ax\equiv 1{\pmod {m}},$

შეგვიძლია $x$ აღვნიშნოთ როგორც $a^{-1}$.

უნდა აღვნიშნოთ, რომ მოდულარული ინვერსი ყოველთვის არ არსებობს. მაგალითად, დავუშვათ $m=4$ და $a=2$, თუ შევამოწმებთ $modm$ - ის ყველა მნიშვნელობას, ვნახავთ, რომ ვერ ვიპოვით $a^{-1}$-ს, რომელიც აკმაყოფილებს ზემოთხსენებულ ტოლობას. დამტკიცებულია, რომ მოდულარული ინვერსიული რიცხვი მხოლოდ და მხოლოდ მაშინ არსებობს, როდესაც $n$ და $m$ არიან ურთიერთმარტივი რიცხვები, ანუ მათი უ.ს.ჯ $1$-ია ($gcd(n,m)=1$).

მოდულარული ინვერსის პოვნის ერთ-ერთი მეთოდი იყენებს ევკლიდეს გაფართოებული ალგორითმს.

განვიხილოთ დიოფანტინის შემდეგი განტოლება: $ax+my=1$

როდესაც $gcd(n,m)=1$, მოცემულ განტოლებას აქვს ამონახსნი, რომლის მოძებნა ევკლიდეს გაფართოებული ალგორითმით შეიძლება. შევნიშნოთ, რომ $gcd(n,m)=1$ არის ასევე მოდულარული ინვერსის არსებობის პირობა.

თუ ორივე მხრიდან ავიღებთ $modm$-ს, მაშინ $my$ გაქრება და მივიღებთ $ax=1modm$, ანუ მოდულარული ინვერსი $a$ რიცხვისა არის $x$.

რესურსები ინტერნეტში

• e-maxx
• cp-algorithms