Основное содержание
Информатика
Course: Информатика > Модуль 2
Урок 5: Модульная арифметика- Что такое модульная арифметика?
- Оператор модуля
- Испытание по модульной арифметике
- Равенство по модулю
- Отношение равенства
- Отношения эквивалентности
- Теорема о делимости целых чисел с остатком
- Сложение и вычитание по модулю
- Сложение по модулю
- Испытание по теме «Модульная арифметика» (сложение и вычитание)
- Умножение по модулю
- Умножение по модулю
- Возведение в степень по модулю
- Быстрое возведение в степень по модулю
- Быстрое возведение в степень по модулю
- Обратное число по модулю
- Алгоритм Евклида
Сложение и вычитание по модулю
Рассмотрим свойство аддитивности модульной арифметики.
(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
ЛЧ = (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
ПЧ = (14 mod 5 + 17 mod 5) mod 5
ПЧ = (4 + 2) mod 5
ПЧ = 1
ЛЧ = ПЧ = 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
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
ЛЧ = (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
ЛЧ=ПЧ= (R1 + R2) mod C
Вычитание по модулю
Похожим образом можно доказать свойство вычитания по модулю.
(A - B) mod C = (A mod C - B mod C) mod C
Хотите присоединиться к обсуждению?
Пока нет ни одной записи.