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

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

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

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

შევნიშნოთ, რომ $a^{-1}$ ყოველთვის არ არსებობს. მაგალითად, დავუშვათ $m=4$ და $a=2$, თუ შევამოწმებთ ${\begin{aligned}x{\pmod {m}}\end{aligned}}$ - ის ყველა მნიშვნელობას, ვნახავთ, რომ ვერ ვიპოვით $x$-ს, რომელიც აკმაყოფილებს ზემოთხსენებულ ტოლობას. დამტკიცებულია, რომ ${\begin{aligned}a^{-1}{\pmod {m}}\end{aligned}}$ მხოლოდ და მხოლოდ მაშინ არსებობს, როდესაც $a$ და $m$ არიან ურთიერთმარტივი რიცხვები, ანუ მათი უ.ს.გ $1$-ია ($(a,m)=1$).

გამოთვლა

• განვიხილოთ დიოფანტინის შემდეგი განტოლება: $ax+my=1$. როდესაც $(a,m)=1$, მოცემულ განტოლებას აქვს ამონახსნი, რომლის მოძებნა ევკლიდეს გაფართოებული ალგორითმით შეიძლება. შევნიშნოთ, რომ $(a,m)=1$ არის ასევე მოდულით შებრუნებული რიცხვი არსებობის პირობა. თუ ორივე მხრიდან ავიღებთ ${\begin{aligned}{\pmod {m}}\end{aligned}}$-ს, მაშინ $my$ გაქრება და მივიღებთ :${\begin{aligned}ax&\equiv 1{\pmod {m}}\end{aligned}}$, ანუ $x$ არის მოდულით შებრუნებული რიცხვი.

• ფერმას მცირე თეორემა გვეუბნება, რომ ${\begin{aligned}a^{m-1}&\equiv 1{\pmod {m}}\end{aligned}}$, აქედან გამომდინარე ${\begin{aligned}aa^{m-2}&\equiv 1{\pmod {m}}\end{aligned}}$, შესაბამისად მოდულით შებრუნებული რიცხვი გამოდის ${\begin{aligned}a^{m-2}{\pmod {m}}\end{aligned}}$.

ლიტერატურა

• Competitive Programmer's Handbook - Antti Laaksonen. 2018 (გვ. 202)

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

• e-maxx
• cp-algorithms