Основное содержание
Информатика
Course: Информатика > Модуль 2
Урок 5: Модульная арифметика- Что такое модульная арифметика?
- Оператор модуля
- Испытание по модульной арифметике
- Равенство по модулю
- Отношение равенства
- Отношения эквивалентности
- Теорема о делимости целых чисел с остатком
- Сложение и вычитание по модулю
- Сложение по модулю
- Испытание по теме «Модульная арифметика» (сложение и вычитание)
- Умножение по модулю
- Умножение по модулю
- Возведение в степень по модулю
- Быстрое возведение в степень по модулю
- Быстрое возведение в степень по модулю
- Обратное число по модулю
- Алгоритм Евклида
Что такое модульная арифметика?
Введение в модульную математику
Когда мы делим одно целое число на другое, мы получаем примерно вот такое выражение:
A — делимое
B — делитель
Q — частное
R — остаток
B — делитель
Q — частное
R — остаток
Иногда при делении A на B нас интересует только остаток.
В этом случае используется операция «взятия остатка» или «деления по модулю» (обозначается как mod).
В этом случае используется операция «взятия остатка» или «деления по модулю» (обозначается как mod).
Если взять те же A, B, Q и R, что и в примере выше, получим: A, start text, space, m, o, d, space, end text, B, equals, R
Здесь A разделить по модулю B равняется R. Таким образом, B в такой операции называется модулем.
Например:
Наглядное представление модуля при помощи циферблата
Смотрите, что произойдёт, если мы начнём увеличивать на 1, а затем разделим на 3.
Остаток начинается с 0, а затем на каждом шаге он будет увеличиваться на 1, пока не станет на 1 меньше делителя. Затем последовательность начнёт повторяться.
Заметив эту закономерность, мы можем представить деление по модулю при помощи кругов.
Запишем 0 сверху круга, а затем по часовой стрелке будем подписывать: 0, 1, …, до числа, на единицу меньшего, чем модуль.
Например, часовой циферблат, на котором вместо 12 будет стоять 0, — это круг для деления по модулю 12.
Чтобы найти, чему равно A, start text, space, m, o, d, space, end text, B, можно проделать следующие шаги:
- Строим циферблат для модуля B.
- Начиная с 0, движемся по циферблату на A делений.
- Число, на котором мы остановимся, и будет ответом.
(Если число положительное, мы движемся по циферблату по часовой стрелке, если число отрицательное, то мы движемся против часовой стрелки.)
Пример
8, start text, space, m, o, d, space, end text, 4, equals, question mark
Для модуля 4 мы рисуем циферблат с числами 0, 1, 2, 3.
Начинаем с 0 и делаем 8 шагов по часовой стрелке: 1, 2, 3, 0, 1, 2, 3, 0.
Начинаем с 0 и делаем 8 шагов по часовой стрелке: 1, 2, 3, 0, 1, 2, 3, 0.
Мы остановились на числе 0, следовательно, 8, start text, space, m, o, d, space, end text, 4, equals, 0.
7, start text, space, m, o, d, space, end text, 2, equals, question mark
Для модуля 2 мы рисуем циферблат с числами 0, 1.
Начинаем с 0 и делаем 7 шагов по часовой стрелке: 1, 0, 1, 0, 1, 0, 1.
Начинаем с 0 и делаем 7 шагов по часовой стрелке: 1, 0, 1, 0, 1, 0, 1.
Мы остановились на 1, значит, 7, start text, space, m, o, d, space, end text, 2, equals, 1.
minus, 5, start text, space, m, o, d, space, end text, 3, equals, question mark
Для модуля 3 мы рисуем циферблат с числами 0, 1, 2.
Начинаем с 0 и делаем 5 шагов против часовой стрелки (число −5 — отрицательное): 2, 1, 0, 2, 1.
Начинаем с 0 и делаем 5 шагов против часовой стрелки (число −5 — отрицательное): 2, 1, 0, 2, 1.
Мы остановились на 1, значит, minus, 5, start text, space, m, o, d, space, end text, 3, equals, 1.
Заключение
Если взять выражение A, start text, space, m, o, d, space, end text, B и увеличить A на число, кратное B, результат не изменится, то есть:
A, start text, space, m, o, d, space, end text, B, equals, left parenthesis, A, plus, K, dot, B, right parenthesis, start text, space, m, o, d, space, end text, B для любого целого K.
Например:
Примечания для читателя
Деление по модулю в языках программирования и калькуляторах
Во многих языках программирования и калькуляторах есть операция деления по модулю, часто она обозначается символом %. Если вы делите по модулю отрицательное число, в некоторых языках программирования ответ может также получиться отрицательным.
Например:
Например:
-5 % 3 = -2.
Сравнение по модулю
Вы можете встретить следующее выражение:
A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
Это значит, что A равно B по модулю C. Это выражение очень похоже на то, которым мы пользовались выше, но есть и отличия.
В следующей статье мы объясним, что это значит и как это связано с уже известным нам выражением.
Хотите присоединиться к обсуждению?
Пока нет ни одной записи.