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
ЛЧ = левая часть равенства
ПЧ = правая часть равенства
ЛЧ = (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
ЛЧ = ПЧ = 1

Интуитивное понимание сложения по модулю

Посмотрите на изображение ниже. Если мы хотим вычислить 12+9 mod 7, нам достаточно будет пройти по модульному кругу 12+9 шагов по часовой стрелке (как показано на нижнем левом круге).
mod
Мы можем сократить перемещения, заметив, что через каждые 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
ЛЧ=ПЧ= (R1 + R2) mod C

Вычитание по модулю

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

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

Хотите присоединиться к обсуждению?

Пока нет ни одной записи.
Знаете английский? Нажмите здесь, чтобы увидеть обсуждение, которое происходит на английской версии сайта.