Что такое множество классов вычетов по модулю n?
Что такое сравнимы 2 числа по модулю я знаю, это когда a ≡ b (mod n) если n делит (a - b)
Что такое множество классов вычетов по модулю n?
с источников я понял что обозначаеться как Zn, где n - это и есть модуль.
пример Zn = {[0], [1], [2]}, каждый єлемент называеться классом эквивалентности?
И что такое класс вычетов? это когда в каждом классе єквивалентности есть множество в котором каждые 2 пары элементов сравнимы по модулю? пример: [0] = [....-6,-3,0, 3,6.....] тут модулю n = 3.
И что в теме сравнимости значит этот символ "⊕"???. это операция с классами эквивалентности?
Ответы (1 шт):
Множество классов вычетов по модулю m - это множество чисел 0,1,...,m-1. Обозначается 
На множестве Z/mZ определены операции сложения, вычитания, умножения и деления. Я обозначу их [+], [-], [*] и [/], чтобы отличать от обчных операций сложения и умножения целых чисел:
a [+] b = (a+b)%m- остаток от деления обычной суммыaиbнаm,a [*] b = (a*b)%m- остаток от деления обычного произведенияaиbнаm,[-]a = m - a, и[-]0 = 0. Соответственноa [-] b = a [+] ([-]b)
Деление - самая хитрая операция в множестве вычетов. a [/] b - это такое число c, что b [*] c = a. Так вот, в отличие от целых чисел, которые делятся друг на друга довольно редко, классы вычетов делятся друг на друга почти всегда. Для этого необходимо и достаточно, чтобы a и b не имели общих делителей с m. Если m - простое число, то все ненулевые пары a и b можно делить. Для деления Z/mZ используется расширенный алгоритм Евклида.
Как это связано с классами эквивалентности. Возьмем ваш пример Z3 = {[0],[1],[2]}
Класс эквивалентности [0] обозначает все те целые числа, которые при делении на 3 дадут остаток 0: [0] == {0, ±3, ±6, ±9, ...}
Класс эквивалентности [1] обозначает все те целые числа, которые при делении на 3 дадут остаток 1: [1] == {1, -2, 4, -5, 7, -8, 10 ...}
Класс эквивалентности [2] обозначает все те целые числа, которые при делении на 3 дадут остаток 2: [2] == {2, -1, 5, -4, 8, -7, 11 ...}
Операции с классами эквивалентности определяются так (для определённости рассмотрим сумму): давайте возьмём из каждого класса по одному представителю, сложим их и в качестве результата возьмём класс эквивалентности получившейся суммы. Например [1] [+] [2] - возьмём из [1] число 1, а из [2] возьёмем 2. 1+2 = 3. Класс эквивалентности, к которому принадлежит 3 - это [0]. Следовательно, [1] [+] [2] = [0]
Несложно доказать, что эти операции сводятся к операциям по модулю, как я написал выше, за исключением деления. Поэтому в реальной жизни никто не морочит себе голову классами эквивалетности, а просто рассматривают числа по модулю.