Модулярная арифметика: Математика остатков
Что такое модулярная арифметика?
Модулярная арифметика — это система счисления, в которой числа «оборачиваются», достигнув определённого значения, называемого модулем. Представь себе часы — после 12 мы снова возвращаемся к 1!
Формальное определение: Для целых чисел $a$, $b$ и положительного целого числа $n$ мы говорим:
$$a \equiv b \pmod{n}$$
что читается как «$a$ сравнимо с $b$ по модулю $n$» тогда и только тогда, когда $n$ делит $(a - b)$. Иначе говоря, $a$ и $b$ имеют одинаковый остаток при делении на $n$.
$$a \equiv b \pmod{n}$$
что читается как «$a$ сравнимо с $b$ по модулю $n$» тогда и только тогда, когда $n$ делит $(a - b)$. Иначе говоря, $a$ и $b$ имеют одинаковый остаток при делении на $n$.
Примеры из жизни
- 🕐 Часы: mod 12
- 📅 Дни недели: mod 7
- 📆 Месяцы: mod 12
- 🔐 Криптография (шифрование RSA)
- 📊 ISBN/штрих-код — контрольные цифры
🕐 Аналогия с часами
Представь часы, которые показывают только часы от 0 до 11 (мы используем 0 вместо 12 для математического удобства). Если сейчас 9 часов и мы прибавим 5 часов, мы не получим 14 часов — мы получим 2 часа!
Математически: $9 + 5 = 14$, а $14 \equiv 2 \pmod{12}$, потому что $14 \div 12 = 1$ с остатком $2$.
Перетащи ползунок, чтобы прибавить часы к 9 и увидеть, как стрелка оборачивается!
Интерактивная визуализация — доступна в полном уроке