If you're seeing this message, it means we're having trouble loading external resources on our website.

თუ ვებფილტრს იყენებთ, დარწმუნდით, რომ *.kastatic.org და *.kasandbox.org დომენები არ არის დაბლოკილი.

ძირითადი მასალა

მოდულარული შებრუნებულები

რა არის შებრუნებული?

გავიხსენოთ, რომ რიცხვი გამრავლებული მის შებრუნებულზე უდრის 1-ს. ელემენტარული არითმეტიკიდან ვიცით, რომ:
  • A რიცხვის შებრუნებული არის 1/A, რადგან A * 1/A = 1 (ანუ, 5-ის შებრუნებული არის 1/5)
  • 0-ის გარდა ყველა რიცხვს გააჩნია შებრუნებული
  • რიცხვის გამრავლება A-ს შებრუნებულზე იგივეა, რაც A-ს გაყოფა (ანუ, 10/5 არის იგივე, რაც 10* 1/5)

რა არის მოდულური შებრუნებული?

მოდულარულ არითმეტიკაში არ გვაქვს გაყოფის ოპერაცია. თუმცა, გვაქვს მოდულარული შებრუნებულები.
  • A (mod C)-ს მოდულარული შებრუნებული არის A^-1
  • (A * A^-1) ≡ 1 (mod C) იგივეა, რაც (A * A^-1) mod C = 1
  • მხოლოდ C-ს თანამარტივ რიცხვებს (რიცხვებს, რომლებიც არ იზიარებენ მარტივ გამყოფებს C-სთან) აქვთ მოდულარული შებრუნებული (mod C)

როგორ ვიპოვოთ მოდულური შებრუნებული

პირდაპირი მეთოდი A (mod C)-ს მოდულარული შებრუნებულის საპოვნელად არის:
ნაბიჯი 1. გამოთვალეთ A * B mod C, B-ს მნიშვნელობებისთვის 0-იდან C-1-მდე
ნაბიჯი 2. A mod C-ს მოდულარული შებრუნებული არის B მნიშვნელობა, რომელიც შემდეგ გამოსახულებას ხდის ჭეშმარიტს: A * B mod C = 1
აღვნიშნოთ, რომ წევრ B mod C-ს შეუძლია მხოლოდ მთელი რიცხვების მნიშვნელობების მიღება 0-იდან C-1-მდე, ასე რომ, B-ს უფრო დიდი მნიშვნელობებისთვის შემოწმება ზედმეტია.

მაგალითი: A=3, C=7

ნაბიჯი 1. გამოთვალეთ A * B mod C, B-ს მნიშვნელობებისთვის 0-იდან C-1-მდე

3 * 0 ≡ 0 (mod 7)
3 * 1 ≡ 3 (mod 7)
3 * 2 ≡ 6 (mod 7)
3 * 3 ≡ 9 ≡ 2 (mod 7)
3 * 4 ≡ 12 ≡ 5 (mod 7)
3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7)  <------ ​ვიპოვეთ შებრუნებული!
3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)

ნაბიჯი 2. A mod C-ს მოდულარული შებრუნებული არის B მნიშვნელობა, რომელიც ხდის შემდეგ გამოსახულებას ჭეშმარიტს: A * B mod C = 1

5 არის 3 mod 7-ის მოდულარული შებრუნებული, რადგან 5*3 mod 7 = 1
მარტივია!
გავაკეთოთ კიდევ ერთი მაგალითი, სადაც არ ვპოულობთ შებრუნებულს.

მაგალითი: A=2 C=6

ნაბიჯი 1. გამოთვალეთ A * B mod C, B-ს მნიშვნელობებისთვის 0-იდან C-1-მდე

2 * 0 ≡ 0 (mod 6)
2 * 1 ≡ 2 (mod 6)
2 * 2 ≡ 4 (mod 6)
2 * 3 ≡ 6 ≡ 0 (mod 6)
2 * 4 ≡ 8 ≡ 2 (mod 6)
2 * 5 ≡ 10 ≡ 4 (mod 6)

ნაბიჯი 2. A mod C-ს მოდულარული შებრუნებული არის B მნიშვნელობა, რომელიც ხდის შემდეგ გამოსახულებას ჭეშმარიტს: A * B mod C = 1

B-ს არც ერთი მნიშვნელობა არ ხდის შემდეგ გამოსახულებას ჭეშმარიტს: A * B mod C = 1. ასე რომ, A-ს არ გააჩნია არცერთი მოდულური შებრუნებული (mod 6).
ეს იმიტომ, რომ 2 არ არის 6-ის თანამარტივი (ისინი იზიარებენ მარტივ მამრავლ 2-ს).

ეს მეთოდი ნელი ჩანს...

არსებობს გაცილებით უფრო სწრაფი მეთოდი A (mod C)-ს შებრუნებულის საპოვნელად, რომელსაც განვიხილავთ შემდეგ სტატიებში ევკლიდეს განზოგადებულ ალგორითმზე.