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

ვთქვათ, 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

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

უფრო მოკლე გზას ვირჩევთ იმის დაკვირვებით, რომ ყოველ 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

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