მოდულით შებრუნებული რიცხვი: განსხვავება გადახედვებს შორის

ისტორიის ინტერაქციულად გადახედვა

[შეუმოწმებელი ვერსია]

← წინა ცვლილება შემდეგი ცვლილება →

შიგთავსი ამოიშალა შიგთავსი დაემატა

ვიზუალურივიკიტექსტი

შიდახაზური

21:00, 7 სექტემბერი 2020-ის ვერსია

მოდულით შებრუნებული რიცხვი $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}}$ მხოლოდ და მხოლოდ მაშინ არსებობს, როდესაც $n$ და $m$ არიან ურთიერთმარტივი რიცხვები, ანუ მათი უ.ს.გ $1$ -ია.

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

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

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

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

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

@@ ხაზი 1: / ხაზი 1: @@
 {{DISPLAYTITLE:მოდულით შებრუნებული რიცხვი}}
-'''მოდულარული ინვერსიული რიცხვი ან მოდულარული ინვერსი''' <math>a</math> რიცხვისა არის ისეთი მთელი <math>x</math> რიცხვი, რომ
+'''მოდულით შებრუნებული რიცხვი''' <math>a</math> რიცხვისა მოდულით <math>m</math> არის ისეთი მთელი <math>x</math> რიცხვი, რომ
 :<math>ax \equiv 1 \pmod{m},</math>
@@ ხაზი 7: / ხაზი 7: @@
 შეგვიძლია <math>x</math> აღვნიშნოთ როგორც <math>a^{-1}</math>.
-უნდა აღვნიშნოთ, რომ მოდულარული ინვერსი ყოველთვის არ არსებობს. მაგალითად, დავუშვათ <math>m=4</math> და <math>a=2</math>,  თუ შევამოწმებთ <math>mod m</math> - ის  ყველა მნიშვნელობას, ვნახავთ, რომ ვერ ვიპოვით <math>a^{-1}</math>-ს, რომელიც აკმაყოფილებს ზემოთხსენებულ ტოლობას. დამტკიცებულია, რომ მოდულარული ინვერსიული რიცხვი მხოლოდ და მხოლოდ მაშინ არსებობს, როდესაც <math>n</math> და <math>m</math> არიან ურთიერთმარტივი რიცხვები, ანუ მათი უ.ს.ჯ <math>1</math>-ია (<math>gcd(n,m)=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>n</math> და <math>m</math> არიან ურთიერთმარტივი რიცხვები, ანუ მათი უ.ს.გ <math>1</math>-ია.
-მოდულარული ინვერსის პოვნის ერთ-ერთი მეთოდი იყენებს ევკლიდეს გაფართოებული ალგორითმს.
+მოდულით შებრუნებული რიცხვის პოვნის ერთ-ერთი მეთოდი იყენებს ევკლიდეს გაფართოებული ალგორითმს.
 განვიხილოთ დიოფანტინის შემდეგი განტოლება: <math>ax+my=1</math>
-როდესაც <math>gcd(n,m)=1</math>, მოცემულ განტოლებას აქვს ამონახსნი, რომლის მოძებნა ევკლიდეს გაფართოებული ალგორითმით შეიძლება. შევნიშნოთ, რომ <math>gcd(n,m)=1</math> არის ასევე მოდულარული ინვერსის არსებობის პირობა.
+როდესაც <math>gcd(a,m)=1</math>, მოცემულ განტოლებას აქვს ამონახსნი, რომლის მოძებნა ევკლიდეს გაფართოებული ალგორითმით შეიძლება. შევნიშნოთ, რომ <math>gcd(a,m)=1</math> არის ასევე მოდულით შებრუნებული რიცხვი არსებობის პირობა.
-თუ ორივე მხრიდან ავიღებთ <math>mod m</math>-ს, მაშინ <math>my</math> გაქრება და მივიღებთ <math>ax = 1 mod m</math>, ანუ მოდულარული ინვერსი <math>a</math> რიცხვისა არის <math>x</math>.
+თუ ორივე მხრიდან ავიღებთ <math>\begin{align}\pmod m\end{align}</math>-ს, მაშინ <math>my</math> გაქრება და მივიღებთ :<math> \begin{align}ax &\equiv 1\pmod m\end{align}</math>, ანუ მოდულით შებრუნებული რიცხვი <math>a</math> რიცხვისა მოდულით <math>m</math> არის <math>x</math>.
 == რესურსები ინტერნეტში ==
 * [http://e-maxx.ru/algo/ e-maxx]