Что такое калькулятор модулярной арифметики?
Модулярная арифметика — это «арифметика часов»: числа «зацикливаются» после того, как достигают фиксированного модуля n. Этот калькулятор вычисляет выражение вида (a op b) mod n, где операцией может быть сложение, вычитание, умножение или просто приведение одного числа a по модулю n. Результатом всегда становится наименьший неотрицательный остаток — число от 0 до n − 1.
Как пользоваться
Введите значение a, выберите операцию, задайте b (не учитывается в режиме «Только по модулю») и укажите модуль n. Сначала калькулятор вычисляет само выражение, а затем приводит его по модулю n. Отрицательные результаты «оборачиваются» в стандартный диапазон 0…n−1, поэтому \(-1 \bmod 12\) даёт 11, а не −1.
Разбор формулы
Основное соотношение — это $$r = (a \mathbin{\text{op}} b) \bmod n.$$ Поскольку остаток в «программистском» стиле может оказаться отрицательным, мы используем евклидову форму $$r = ((x \bmod n) + n) \bmod n,$$ гарантирующую неотрицательный ответ. Именно так принято в теории чисел, криптографии и хешировании.
Пример с решением
Пусть \(a = 17\), операция — сложение, \(b = 25\) и \(n = 12\). Сначала считаем \(17 + 25 = 42\). Затем \(42 \bmod 12\): $$42 = 3 \times 12 + 6,$$ поэтому остаток равен 6. На 12-часовом циферблате «17 + 25 часов» приведут к отметке 6.
Частые вопросы
Что означает «mod»? Это остаток от деления. \(13 \bmod 5 = 3\), потому что \(13 = 2 \times 5 + 3\).
Почему моё отрицательное число стало положительным? Мы возвращаем наименьший неотрицательный остаток. Например, \(-7 \bmod 5 = 3\), так как, прибавив 5 дважды (\(-7 + 10 = 3\)), мы попадаем в диапазон 0…4.
А если n = 1? Любое целое число сравнимо с 0 по модулю 1, поэтому результат всегда равен 0.
