1

Что такое сравнимы 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
  • 2
    На сколько понимаю, класс вычетов по модулю n - множество всех целых чисел, сравнимых между собой по модулю n. Все подобные классы и составляю множество классов вычетов по модулю n. Их будет, собственно, ровно n. 13 мая 2021 в 10:56

1 ответ 1

2

Множество классов вычетов по модулю m - это множество чисел 0,1,...,m-1. Обозначается Z/mZ

На множестве 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]

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.