1.2.2. Группа подстановок
Подстановкой n-ой степени называется взаимно однозначное отображение множества n элементов на себя.
Пример. Множество
X={x1,x2,x3}
имеет 6 перестановок: x1,x2,x3;
x1,x3,x2;
x2,x1,x3;
x2,x3,x1;
x3,x1,x2;
x3,x2,x1.
Число возможных подстановок равно числу
перестановок. Пусть запись
определяет одну из 6 возможных подстановок
и означает, что x1
переходит в x2,
x2 переходит в
x3, x3
переходит в x1.
Введем следующие обозначения для всех
возможных подстановок:
a=
b=
c=
d=
e=
f=
Введем операцию произведения (×) подстановок. Результатом произведения подстановок a и b является подстановка, получаемая в результате последовательного выполнения сначала подстановки a, а затем подстановки b. Например,
c×b= × = =e.
Результаты выполнения операции произведения подстановок 3-ей степени сведены в таблицу 1.1
Произведение подстановок ассоциативно, т.е. a´(b´j)=(a´b)´j, но не коммутативно a´b¹b´a (таблица, задающая операцию произведения подстановок, не симметрична относительно главной диагонали).
Подстановка
1=
называется тождественной и играет роль
единицы. Результатом произведения любой
подстановки a на
тождественную подстановку является
подстановка a.
Таблица 1.1
Произведение подстановок
|
a |
b |
c |
d |
e |
f |
a |
a |
b |
c |
d |
e |
f |
b |
b |
a |
d |
c |
f |
e |
c |
c |
e |
a |
f |
b |
d |
d |
d |
f |
b |
e |
a |
c |
e |
e |
c |
f |
a |
d |
b |
f |
f |
d |
e |
b |
c |
a |
Для
любой подстановки a=
существует обратная подстановка a-1,
получаемая из a путем
перестановки строк - a-1=
.
Результатом произведения a´a-1=1
является тождественная подстановка
(a´a-1=1).
Итак, для оерации произведения подстановок n-ой степени (n³3) выполняется (1), (3) и (4). При этом (2) не выполняется. Следовательно, алгебра, носителем которой является множество подстановок n-ой степени (n³3), а сигнатура состоит из одной бинарной операции произведения подстановок, является группой.
1.2.3. Кольцо вычетов
Целые числа 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)=ijn2+(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=<Z4,*,+> представлены в табл.1.2-1.4 соответственно. Делителями нуля является пара элементов a=2,b=2.
