Модульная арифметика
В математике модульная арифметика — это система арифметики для целых чисел , в которой числа «зацикливаются» при достижении определенного значения, называемого модулем . Современный подход к модульной арифметике был разработан Карлом Фридрихом Гауссом в его книге Disquisitiones Arithmeticae , опубликованной в 1801 году.
Знакомое использование модульной арифметики в 12-часовом формате , в котором день делится на два 12-часовых периода. Если сейчас 7:00, то через 8 часов будет 3:00. Простое сложение дало бы 7 + 8 = 15 , но часы "переходят" каждые 12 часов. Поскольку число часов начинается заново после того, как оно достигает 12, это арифметика по модулю 12. С точки зрения приведенного ниже определения, 15 сравнимо с 3 по модулю 12, поэтому «15:00» на 24-часовом формате отображается как «3:00». " в 12-часовом формате.
Для заданного целого числа n > 1 , называемого модулем , два целых числа a и b называются конгруэнтными по модулю n , если n является делителем их разности (т. е. если существует целое число k такое, что a − b = kn ).
Конгруэнтность по модулю n является отношением конгруэнтности , что означает, что это отношение эквивалентности , которое совместимо с операциями сложения , вычитания и умножения . Сравнение по модулю n обозначается:
Скобки означают, что (mod n ) применяется ко всему уравнению, а не только к правой части (здесь b ). Это обозначение не следует путать с обозначением b mod n (без круглых скобок), которое относится к операции по модулю . В самом деле, b mod n обозначает уникальное целое число a такое, что 0 ≤ a < n и (т. е. остаток от деления на ).
явно показывая его связь с евклидовым делением . Однако здесь b не обязательно должен быть остатком от деления a на n . Вместо этого утверждение a ≡ b (mod n ) утверждает, что a и b имеют одинаковый остаток при делении на n . Это,
