Введение в модульную арифметику
Модульная арифметика — это система арифметики для целых чисел, где числа «оборачиваются» после достижения определенного значения, называемого модулем. Эта математическая структура является основополагающей для теории чисел и имеет важные применения в криптографии, информатике и других областях.
Определение
В модульной арифметике мы говорим, что два целых числа a и b сравнимы по модулю n, если они дают одинаковый остаток при делении на n. Мы записываем это как:
a ≡ b (mod n)
Это читается как «a сравнимо с b по модулю n». Математически это означает, что n делит разность a и b, или:
a ≡ b (mod n) тогда и только тогда, когда a - b = kn для некоторого целого k
Ключевые понятия
- Классы вычетов: Для данного модуля n все целые числа можно разделить на n различных классов эквивалентности: {0, 1, 2, ..., n-1}. Каждое целое число принадлежит точно одному из этих классов.
- Часовая арифметика: 12-часовые часы — это идеальный пример модульной арифметики с модулем 12. После 12 часы «оборачиваются» обратно к 1.
- Модульные операции: Сложение, вычитание и умножение в модульной арифметике следуют определенным правилам, которые сохраняют отношение сравнимости.
- Модульные обратные: Для некоторых значений мы можем определить деление в модульной арифметике, используя понятие модульных мультипликативных обратных.