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

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

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

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

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

გამოთვლა

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

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

ლიტერატურა

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

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

• e-maxx
• cp-algorithms