Кольцо вычетов по модулю m

Question

Кольцо вычетов по модулю m

Евгений Мастер (1133), на голосовании 10 лет назад

Здраствуйте) объясните своими словами как вычесляеться кольцо Z? ( внизу m) Кольцо вычетов по модулю mЦелочисленный тип компьютера в точности соответствует важнейшему понятию математики - понятию кольца вычетов по модулю m. В качестве mвыступает число 232 = 4294967296. В математике кольцо Zmопределяется следующим образом. Все множество целых чисел Zразбивается на mклассов, которые называются классами эквивалентности. Каждый класс содержит числа, попарная разность которых делится на m. Первый класс содержит числа
{...,-2m,-m,0,m,2m, ..}

второй
{...,-2m+1, -m+1, 1, m+1, 2m+1, ..}

последний
{...,-m-1, -1, m-1, 2m-1, 3m-1, ..}

Элементами кольца Zmявляются классы эквивалентности. Их ровно m, так что, в отличие от множества целых чисел Z, кольцо Zmсодержит конечное число элементов. Операции с классами выполняются следующим образом: надо взять по одному представителю из каждого класса, произвести операцию и определить, в какой класс попадает результат. Этот класс и будет результатом операции. Легко показать, что он не зависит от выбора представителей. и вообще я прохожу курсы по программированию задали эту фигню, это вообще нужно мне знать????

Answer 1

Для начала неплохо бы спросить википедию: Сравнение по модулю
С точки зрения программиста классы эквивалентности - это просто остатки от деления на число m.

Операции над числами а и b:
1. Сложение: a+b сравнить с m, если больше, то вычесть m из суммы, или просто взять остаток от деления (a+b) mod m
2. Вычитание: a-b если результат < 0, то добавить m
3. Умножение: a*b - нужно взять от этого числа остаток от деления на m
4. Деление: всё непросто, может быть несколько вариантов, когда m не простое