Основное содержание

Информатика

Course: Информатика > Модуль 2

Урок 5: Модульная арифметика

Что такое модульная арифметика?

Классная комната Google

Введение в модульную математику

Когда мы делим одно целое число на другое, мы получаем примерно вот такое выражение:

start fraction, A, divided by, B, end fraction, equals, Q, start text, space, о, с, т, а, т, о, к, space, end text, R

A — делимое
B — делитель
Q — частное
R — остаток

Иногда при делении A на B нас интересует только остаток.
В этом случае используется операция «взятия остатка» или «деления по модулю» (обозначается как mod).

Если взять те же A, B, Q и R, что и в примере выше, получим: A, start text, space, m, o, d, space, end text, B, equals, R

Здесь A разделить по модулю B равняется R. Таким образом, B в такой операции называется модулем.

Например:

$\begin{array}{rcl} \frac{13}{5} & = & 2 остаток 3 \\ 13 mod 5 & = & 3 \end{array}$ ‍

Наглядное представление модуля при помощи циферблата

Смотрите, что произойдёт, если мы начнём увеличивать на 1, а затем разделим на 3.

$\begin{array}{rcl} \frac{0}{3} & = & 0 остаток 0 \\ \frac{1}{3} & = & 0 остаток 1 \\ \frac{2}{3} & = & 0 остаток 2 \\ \frac{3}{3} & = & 1 остаток 0 \\ \frac{4}{3} & = & 1 остаток 1 \\ \frac{5}{3} & = & 1 остаток 2 \\ \frac{6}{3} & = & 2 остаток 0 \end{array}$ ‍

Остаток начинается с 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, 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.

Мы остановились на 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.

Мы остановились на 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.

Например:

$\begin{array}{r} 3 mod 10 = 3 \\ 13 mod 10 = 3 \\ 23 mod 10 = 3 \\ 33 mod 10 = 3 \end{array}$ ‍

Примечания для читателя

Деление по модулю в языках программирования и калькуляторах

Во многих языках программирования и калькуляторах есть операция деления по модулю, часто она обозначается символом %. Если вы делите по модулю отрицательное число, в некоторых языках программирования ответ может также получиться отрицательным.
Например:

-5 % 3 = -2.

Сравнение по модулю

Вы можете встретить следующее выражение:

A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis

Это значит, что A равно B по модулю C. Это выражение очень похоже на то, которым мы пользовались выше, но есть и отличия.

В следующей статье мы объясним, что это значит и как это связано с уже известным нам выражением.

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

Войти

Сортировать по:

Пока нет ни одной записи.

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