Калькулятор модулярной арифметики

Калькулятор модулярной арифметики

Растущий AI Skill PRO

Введите расчет

Результаты

Наименьший неотрицательный остаток
6
результат лежит в диапазоне от 0 до n − 1
Значение выражения (до взятия по модулю) 42
Модуль n 12

Математическая формула

результат=(((a+b)modn)+n)modn\text{результат} = \left(\left(\left(\text{a} + \text{b}\right) \bmod \text{n}\right) + \text{n}\right) \bmod \text{n}
Статистика использования

Реклама

Сообщить об ошибке на этой странице

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

Модулярная арифметика — это «арифметика часов»: числа «зацикливаются» после того, как достигают фиксированного модуля n. Этот калькулятор вычисляет выражение вида (a op b) mod n, где операцией может быть сложение, вычитание, умножение или просто приведение одного числа a по модулю n. Результатом всегда становится наименьший неотрицательный остаток — число от 0 до n − 1.

Круговое кольцо чисел от 0 до 11 со стрелкой, показывающей, как значения замыкаются по кругу
Модульная арифметика заворачивает числа по кругу размером n.

Как пользоваться

Введите значение 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,$$ гарантирующую неотрицательный ответ. Именно так принято в теории чисел, криптографии и хешировании.

Реклама
Числовая прямая, разбитая на равные блоки, показывающая отображение отрицательных значений в неотрицательные остатки
Отрицательные числа отображаются в тот же наименьший неотрицательный остаток от 0 до n-1.

Пример с решением

Пусть \(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.

Реклама

Больше разобранных примеров с отрицательными числами и умножением

Во всех случаях калькулятор возвращает наименьший неотрицательный остаток \(r\), то есть единственное значение, для которого \(0 \le r < n\) и \(\text{raw} = n\cdot q + r\) при некотором целом \(q\). Модуль \(n\) должен быть положительным целым числом.

Пример 1: вычитание с отрицательным промежуточным результатом

Вычислим \((5 - 23) \bmod 7\).

  1. Промежуточный результат: \(5 - 23 = -18\).
  2. Деление: \(-18 = 7 \cdot (-3) + 3\), so the quotient is \(-3\) and the remainder is \(3\). Check: \(-18 + 21 = 3\).
  3. Итоговый остаток: 3.

Пример 2: умножение

Вычислим \((47 \times 19) \bmod 10\).

  1. Промежуточный результат: \(47 \times 19 = 893\).
  2. Деление: \(893 = 10 \cdot 89 + 3\), so the quotient is \(89\) and the remainder is \(3\).
  3. Итоговый остаток: 3. (Сокращение: при mod 10 важны только последние цифры, а \(7 \times 9 = 63\) оканчивается на 3.)

Пример 3: обычный модуль отрицательного числа

Вычислим \(-29 \bmod 6\).

  1. Исходное значение: \(-29\) (для обычного взятия модуля второй операнд не нужен).
  2. Деление: \(-29 = 6 \cdot (-5) + 1\), so the quotient is \(-5\) and the remainder is \(1\). Check: \(-29 + 30 = 1\).
  3. Итоговый остаток: \(1\).

Обратите внимание, что частное округляется вниз (к минус бесконечности), а не к нулю. Именно это гарантирует, что остаток находится между 0 и \(n-1\).

Сравнение сценариев: одинаковые входные данные, разные операции

a b n Операция Промежуточный результат Итоговый остаток
17 25 12 Сложение 42 = 12·3 + 6 6
17 25 12 Вычитание −8 = 12·(−1) + 4 4
17 25 12 Умножение 425 = 12·35 + 5 5
−7 не используется 5 Обычный модуль −7 = 5·(−2) + 3 3
17 25 1 Умножение 425 = 1·425 + 0 0

При \(n = 1\) любое целое число сравнимо с 0, поэтому результат всегда равен 0.

Примечание: евклидов (наименьший неотрицательный) остаток может отличаться от знакового остатка, который возвращают некоторые языки программирования. В C, C++, Java и JavaScript оператор % отбрасывает дробную часть в сторону нуля, поэтому -7 % 5 даёт \(-2\), тогда как этот калькулятор выдаёт \(3\). Оператор % в Python при положительном модуле даёт \(3\), что совпадает с евклидовым результатом. Два значения отличаются ровно на \(n\) всякий раз, когда знаковый остаток отрицателен.

Последнее обновление:

Самые популярные в разделе Математика и статистика

Все калькуляторы раздела Математика и статистика