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

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

$ax\equiv 1(\mathrm{mod}m),$

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

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

გამოთვლა

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

• ფერმას მცირე თეორემა გვეუბნება, რომ $\begin{array}{cc}{a}^{m-1}& \equiv 1(\mathrm{mod}m)\end{array}$, აქედან გამომდინარე $\begin{array}{cc}a{a}^{m-2}& \equiv 1(\mathrm{mod}m)\end{array}$, შესაბამისად მოდულით შებრუნებული რიცხვი გამოდის $\begin{array}{c}{a}^{m-2}(\mathrm{mod}m)\end{array}$.

ლიტერატურა

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

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

• e-maxx
• cp-algorithms