Сложение и вычитание по модулю

Допустим A=14, B=17, C=5

Давайте проверим: (A + B) mod C = (A mod C + B mod C) mod C
ЛЧ = левая часть равенства
ПЧ = правая часть равенства

ЛЧ = (A + B) mod C
ЛЧ = (14 + 17) mod 5
ЛЧ = 31 mod 5
ЛЧ = 1

ПЧ = (A mod C + B mod C) mod C
ПЧ = (14 mod 5 + 17 mod 5) mod 5
ПЧ = (4 + 2) mod 5
ПЧ = 1

Посмотрите на изображение ниже. Если мы хотим вычислить 12+9 mod 7, нам достаточно будет пройти по модульному кругу 12+9 шагов по часовой стрелке (как показано на нижнем левом круге).

Мы можем сократить перемещения, заметив, что через каждые 7 шагов мы оказываемся в том же самом месте модульного круга. Это значит, что полные обороты по кругу не влияют на конечное положение. Мы можем опустить эти полные круги, вычислив для каждого числа mod 7 (как показано на двух верхних модульных кругах). Это даст нам количество шагов от нуля по часовой стрелке, которое добавляет каждое число к конечному положению.

Теперь нам осталось лишь пройти по часовой стрелке на суммарное количество шагов от каждого числа (как показано на правом нижнем круге). Этот метод работает для любых двух целых чисел и для любого модульного круга.

Докажем, что (A + B) mod C = (A mod C + B mod C) mod C
Для этого нужно показать, что ЛЧ=ПЧ

Из теоремы о делимости с остатком следует, что 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

ЛЧ = (A + B) mod C
ЛЧ = (C * (Q1 + Q2) + R1+ R2) mod C
Мы можем опустить кратные C числа при делении по модулю C
ЛЧ = (R1 + R2) mod C

ПЧ = (A mod C + B mod C) mod C
ПЧ = (R1 + R2) mod C

Похожим образом можно доказать свойство вычитания по модулю.