2.8. Обзор модулярной арифметики
Поскольку проверки на четность используются в дальнейшем довольно часто, следует иметь ясное представление об арифметике, лежащей в основе соответствующих преобразований. Как было показано, сложение по модулю 2 является той арифметической операцией, которая применяется в простых проверках на четность, и оно совпадает с логическим сложением (исключающее ИЛИ). Правила сложения таковы:
системе <нет других чисел, отличных от 0 и 1. Если действовать на павилам обычной арифметики, то нужно разделить результат и взять остаток. Когда позже будет рассматриваться
алгебра линейных уравнении и многочленов с коэффициентами, являющимися числами в системе счисления но модулю 2, то для сложения будет использоваться та же таблица. При умножении применяются следующие правила:
Таким образом, умножение совпадает с логическим И.
Иногда будут применяться вычеты по модулю, отличному от 2. Например, в предыдущем разделе использовались вычеты по модулю 37. В общих чертах теория для любого простого основания 
(например, 37) очень похожа на теорию для основания 2, так что подробности здесь можно опустить. Для понимания соответствующей арифметики и алгебры следует лишь внимательно прочесть начало этого раздела и внести небольшие изменения. При сложении и вычитании по модулю 
следует разделить каждое число на 
и взять положительный остаток.
При умножении по модулю 
(когда 
не простое число) следует быть более осторожным. Предположим, что числа 
сравнимы с числамиа и 
по модулю 
Это означает, что 
или 
для некоторых целых чисел 
Для произведения 
имеем 
Рассмотрим теперь частный случай: 
Имеем 
Но ни а, ни 
не равны 0! Важное свойство умножения, состоящее в том, что если произведение равно 0, то по крайней мере один из сомножителей равен 0, выполнение только для простых оснований. Именно это определяет важность простых оснований. Теперь видно, почему число 37 было столь удобным в разд. 2.7. Читатель должен хорошо разобраться в модулярной арифметике, особенно для простого основания, поскольку в гл. 11 появится более сложная задача построения соответствующей модулярной алгебры. Поэтому в следующем разделе дается еще один пример кодирования такого типа.
