5.3.1. Краткие сведения из теории чисел

Если ,  и  – целые числа и , то говорят, что  делится на  или что  является делителем . Наибольшим общим делителем (НОД) двух чисел называется наибольшее целое положительное число, являющееся делителем обоих этих чисел. Говорят, что два числа взаимно просты, если их НОД равен 1. Для любой пары целых чисел  и  существует единственная пара чисел  (частное) и  (остаток), таких, что , где .

Если два числа  и  дают при делении на число  один и тот же остаток, то говорят, что числа  и  сравнимы по модулю . Сравнение записывается в виде . Эквивалентным определением сравнимости двух чисел является делимость их разности на .

Отметим основные свойства сравнений.

1. Если  и , то .

2. Над сравнениями можно производить операции, аналогичные операциям над равенствами, т.е., если  и , то ,  и , где  – произвольное целое число.

3. Обе части сравнения и их модуль можно разделить на их общий делитель, т.е., если ,  и , то из  следует .

4. Два числа, сравнимые по модулю , сравнимы и по модулю , если  – любой делитель .

Все числа, сравнимые по модулю , образуют класс вычетов по модулю . Любое число в классе называется вычетом по модулю . Всем числам класса вычетов соответствует один и тот же остаток. Так как всего имеется  остатков: , то существует  различных классов вычетов. Вычет, равный самому остатку, называется наименьшим неотрицательным вычетом. Выбрав из каждого класса вычетов по модулю  по одному вычету, получим полную систему вычетов по модулю . Обычно в качестве полной системы вычетов используют наименьшие неотрицательные вычеты: .

Пример 5.1. Пусть , тогда числа  и т.д. образуют класс вычетов по модулю 4. Наименьший вычет в этом классе равен , а полную систему вычетов по модулю 4 образуют числа .

С учетом определенного выше понятия сравнения чисел по модулю  введены операции сложения и умножения чисел по модулю произвольного целого числа .

При этом результат применения операции сложения (умножения) двух чисел по модулю  равен наименьшему вычету класса, к которому принадлежит число, получаемое в результате обычного сложения (умножения) чисел. Другими словами, результат применения операции сложения (умножения) чисел по модулю  равен остатку от деления числа, получаемого при обычном сложении (умножении) чисел, на модуль .

Пример 5.2. При  таблицы сложения и умножения чисел по модулю 5 выглядят следующим образом: