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