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

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

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

მოდულარული შეკრება და გამოკლება

მოდით, შევისწავლოთ მოდულარული არითმეტიკის შეკრების თვისება:

(A + B) mod C = (A mod C + B mod C) mod C

მაგალითი:

ვთქვათ, A=14, B=17, C=5
ვაჩვენოთ, რომ: (A + B) mod C = (A mod C + B mod C) mod C
LHS = ტოლობის მარცხენა (ხელის) მხარე
RHS = ტოლობის მარჯვენა (ხელის) მხარე
LHS = (A + B) mod C
LHS = (14 + 17) mod 5
LHS = 31 mod 5
LHS = 1
LHS = (A + B) mod C
LHS = (14 + 17) mod 5
LHS = 31 mod 5
LHS = 1
LHS = RHS = 1

ინტუიცია მოდულურ შეკრებაზე

დააკვირდით ქვემოთ მოცემულ ფიგურას. თუ გვინდა, გამოვთვალოთ 12+9 mod 7 მაშინ მარტივად შეგვიძლია ვიაროთ მოდულარულ წრეზე 12+9 ნაბიჯიანი მიმდევრობისთვის საათის ისრის მიმართულებით (როგორც ნაჩვენებია ქვედა მარცხენა წრეზე).
mod
უფრო მოკლე გზას ვირჩევთ იმის დაკვირვებით, რომ ყოველ 7 ნაბიჯში იგივე ადგილზე ვხვდებით მოდულარულ წრეზე. ეს შესრულებული ციკლები მოდულარულ წრეზე არაფერს ცვლის ჩვენი საბოლოო ადგილმდებარეობისათვის. უგულებელვყოფთ ამ შესრულებულ ციკლებს წრის ირგვლივ ყველა რიცხვის 7-ზე ნაშთის გამოთვლით (როგორც ნაჩვენებია ზედა მოდულარულ ორ წრეში). ეს მოგვცემს საათის ისრის მიმართულებით გასაკეთებელი ნაბიჯების რიცხვს, 0-ის მიმართ, რომლებმაც წვლილი შეიტანეს საბოლოო ადგილმდებარეობაზე მოდულარული წრის ირგვლივ.
ახლა წრის ირგვლივ უნდა გავიდეთ საათის ისრის მიმართულებით ჯამურად იმდენი ნაბიჯით, რამდენმაც წვლილი შეიტანა თითოეული რიცხვის საბოლოო პოზიციისთვის (როგორც ნაჩვენებია ქვედა მარჯვენა მოდულარულ წრეზე). ეს მეთოდი გამოიყენება, ზოგადად, ნებისმიერ ნატურალურ მთელ რიცხვზე და ნებისმიერ მოდულარულ წრეზე.

მოდულური შეკრების დამტკიცება

დავამტკიცებთ, რომ (A + B) mod C = (A mod C + B mod C) mod C
უნდა ვაჩვენოთ, რომ LHS=RHS
ბეზუს თეორემიდან შეგვიძლია A და B ჩავწეროთ შემდეგნაირად:
A = C * Q1 + R1, სადაც 0 ≤ R1 < C და Q1 არის მთელი რიცხვი. A mod C = R1
B = C * Q2 + R2, სადაც 0 ≤ R2 < C და Q2 არის მთელი რიცხვი. B mod C = R2
(A + B) = C * (Q1 + Q2) + R1+R2
LHS = (A + B) mod C
LHS = (C * (Q1 + Q2) + R1+ R2) mod C
შეგვიძლია, გამოვრიცხოთ C-ს ჯერადები, როდესაც ვიღებთ mod C-ს
LHS = (R1 + R2) mod C
RHS = (A mod C + B mod C) mod C
RHS = (R1 + R2) mod C
LHS=RHS= (R1 + R2) mod C

მოდულური გამოკლება

ანალოგიური დამტკიცება აქვს მოდულურ გამოკლებას

(A - B) mod C = (A mod C - B mod C) mod C