Классы вычетов

Сравнения. Кольца вычетов.

вычеты - это просто остатки от деления на целое число
при делении на 5 могут быть остатки 0, 1, 2, 3, 4
или, как принято в теории чисел, -2,-1, 0, 1, 2
3 делим на получаем остаток или 3 или -2 что абсолютно равноценно

Этот набор возможных остатков и называется кольцом вычетов

Сравнение^[1] по модулю натурального числа n — в теории чисел отношение эквивалентности на кольце целых чисел, связанное с делимостью на n. Факторкольцо по этому отношению называется кольцом вычетов. Совокупность соответствующих тождеств и алгоритмов образует модульную ^[2] (или модулярную) арифметику.

Классы вычетов

Множество всех чисел сравнимых с a по модулю n называется классом вычетов a по модулю n, и обычно обозначается или . Таким образом, сравнение равносильно равенству классов вычетов .

Поскольку сравнение по модулю n является отношением эквивалентности на множестве целых чисел , то классы вычетов по модулю n представляют собой классы эквивалентности; их количество равно n. Множество всех классов вычетов по модулю n обозначается или .

Операции сложения и умножения на индуцируют соответствующие операции на множестве :

Относительно этих операций множество является конечным кольцом, а для простого n — конечным полем.