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

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

შეგვიძლია  აღვნიშნოთ როგორც .   

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

 გამოთვლა 
  განვიხილოთ დიოფანტინის შემდეგი განტოლება: . როდესაც , მოცემულ განტოლებას აქვს ამონახსნი, რომლის მოძებნა ევკლიდეს გაფართოებული ალგორითმით შეიძლება. შევნიშნოთ, რომ  არის ასევე მოდულით შებრუნებული რიცხვი არსებობის პირობა. თუ ორივე მხრიდან ავიღებთ -ს, მაშინ  გაქრება და მივიღებთ :, ანუ  არის მოდულით შებრუნებული რიცხვი.

 ფერმას მცირე თეორემა გვეუბნება, რომ , აქედან გამომდინარე , შესაბამისად მოდულით შებრუნებული რიცხვი გამოდის .

 ლიტერატურა 
  Competitive Programmer's Handbook - Antti Laaksonen. 2018 (გვ. 202)

 რესურსები ინტერნეტში 
 e-maxx
 cp-algorithms

კატეგორია:პროგრამირება
კატეგორია:ალგორითმები
კატეგორია:მათემატიკა
კატეგორია:რიცხვთა თეორია