Сравнение по модулю

Определение

Говорят, что a сравнимо с b по модулю c, если . В этом случае пишут a º b (mod c), или a º b (c).

Пример

21 º 15 (mod 3).

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

Определение

Кольцо остатков по данному модулю n - это множество всех остатков от деления натуральных чисел на данное число n. Это множество обозначают как Z_n.

Название «кольцо остатков» связано с тем, что множество всех остатков удовлетворяет некоторым свойствам, принятым в алгебре. Подробный список этих свойств для краткости здесь приводить не будем.

Например, составим таблицу сложения в кольце остатков по модулю 4. Складывая остатки, результат сложения заменим его остатком от деления на 4.

Например, 1 + 3 заменим 0.

Таблица умножения в том же кольце остатков.

Обратите внимание на то, что в данном кольце остатков произведение двух ненулевых чисел (2 и 2) равно нулю.