2015-04-01
11565
Целые числа a, b сравнимы по модулю n, если при делении на число n эти числа дают один остаток (a mod n = b mod n).
При делении на n возможные значения остатка 0,1,…, n -1.
Обозначим [ k ] – класс сравнимых между собой чисел, дающих при делении на n остаток k. Например, для n =4 образуется четыре класса:
[0]={…-12,-8,-4,0,4,8,12,…},
[1]={…-11,-7,-3,1,5,9,13,…},
[2]={…-6,-2,2,6,10,14,…},
[3]={…-5,-1,3,7,11,15,…}.
Таким образом, при делении на n образуется n классов [0],[1],…,[ n -1]. Эти классы называются классами вычетов по модулю n. Множество Zn ={[0],[1],…, [ n -1]} называется полной системой вычетов. В дальнейшем квадратные скобки будем опускать Zn ={0,1,…, n -1}.
Число из класса [ a ] имеет вид in + a. Выясним, в какой класс попадет сумма чисел из классов [ a ],[ b ]:
in + a + jn + b =(i + j) n +(a + b).
Это число при делении на n дает остаток ((i + j) n +(a + b)) mod n = (a + b) mod n. Таким образом, сумма любых двух чисел из классов [ a ],[ b ] принадлежит классу [(a + b) mod n ]. В соответствии с этим на множестве Zn введем операцию сложения:
a + b =(a + b) mod n; a, b Î Zn.
В этом соотношении слева используется алгебраическая операция над элементами a, b Î Zn. Справа – арифметические операции над числами a, b, n.
Свойства введенной операции сложения:
· операция коммутативна и ассоциативна, поскольку коммутативна и ассоциативна арифметическая операция сложения в правой части соотношения a + b =(a + b) mod n.
· 0 + a = a + 0=(a +0) mod n = a, a Î Zn.
· элемент, противоположный элементу a, определяется следующим образом - a = n - a, т.к. a + (- a)=(- a) + a =(a + n - a) mod n =0.
Таким образом, алгебра A =< Zn,*, + > образует абелевую группу относительно операции сложения.
Теперь выясним, в какой класс попадет произведение чисел из классов [ a ],[ b ]:
(in + a)(jn + b)= ijn 2+(ia + kj) n + ab.
Это число при делении на n дает остаток (ab) mod n.
Поэтому операция умножения на множестве Zn определяется как:
a * b =(ab) mod n.
В этом соотношении слева – алгебраическая операция над элементами a, b Î Zn. Справа – арифметические операции над числами a, b, n.
Свойства введенной операции умножения:
· операция умножения коммутативна и ассоциативна, поскольку коммутативна и ассоциативна арифметическая операция умножения в правой части соотношения a * b =(ab) mod n.
· умножение дистрибутивно относительно сложения a *(b + c)=(a * b) + (a * c) и (a + b)* c =(a * c) + (b * c).
Итак, алгебра A =< Zn,*, + > образует абелевую группу относительно операции сложения, является полугруппой относительно умножения (умножение ассоциативно), и умножение дистрибутивно относительно сложения, следовательно, алгебра A - кольцо.
Такую алгебру называют кольцом вычетов.
Кроме того, в кольце вычетов выполняется условие коммутативности умножения, следовательно, данная алгебра является коммутативным кольцом.
Если n – составное, то кольцо вычетов содержит делители нуля. Действительно, если n = kl, тогда по определению умножения k * l =(kl) mod n =0.
Результаты операций сложения умножения и вычитания в A =< Z 4,*, + > представлены в табл.1.2-1.4 соответственно. Делителями нуля является пара элементов a =2, b =2.
 |
