ALG#04 (Алгебра)

Кольцо вычетов целых чисел.

- конгруэнция на Z. Пусть [a]n – класс эквивалентных элементов относительно ; а остатков: - разные классы.

- множество + операции: . В силу теоремы, что - конгруэнция, введенные операции – введены корректно. - это множество с этими операциями – это кольцо из n элементов.

Для простоты: - наименьший неотрицательный элемент из класса [a] .

Идеалы колец.

Опр: Пусть - кольцо - идеал кольца R, если .

Пример: R=Z, J – четные числа .

Рассматриваем свойства коммутативных колец.

Опр: Идеал I – максимальный идеал, если из условия, что либо J=R.

Утв: Если есть 2 идеала: то:

Док-во:

1. если то для

2. Пусть

Опр: Пусть - сравнение по модулю идеала I:

Теорема: Пусть R- коммутативное кольцо: :

1. Отношение сравнимости - конгруэнция кольца.

2. Если I – max, то кольцо - поле.

Док-во: это отношение эквивалентности, т.к.:

1. Рефлективное: т.е.

Пусть

1. Симметричное:

2. Транзитивное: ; это отношение эквивалентности, значит разбивает кольцо на не пересекающиеся классы:

Определим операции на классах:

Док-во корректности введенных операций:

1. [a]+[b]=a+I+b+I=(a+b)+(I+I)=(a+b)+I=[a+b]

Отношение - конгруэнция на R; значит получается, что - кольцо.

Идеалы кольца целых чисел.

Теорема: Все идеалы кольца целых чисел исчерпываются множествами вида: .

Док-во: что

1. что nZ<Z, т.е. под кольцо

   1. , т.е. (nZ,+) – кососимметричная группа.

   2. т.е. дистрибутивность для данных чисел выполняется в силу того, что она выполняется для всех целых чисел.

2. т.к.

3. Покажем, что любой идеал имеет такой вид, т.е. если

   1. Если I={0}, то n=0, I=0*Z

   2. , т.е. состоит не из одного нуля. если и I есть элементы не равные нулю, то там есть положительные элементы, отличные от нуля. Возьмем наименьшее такое число: . Введем: но .

Теорема: .

Док-во:

1. . Возьмем:

2. Аналогично: если , т.е. . Обратно: .

Следствие: .

Теорема: Идеал nZ – max n – простое число.

Док-во: (от противного) Прямое: Пусть - противоречит с тем, что nZ – max => n – простое.

Обратное: n – простое; Пусть , а т.к. - противоречит тому, что n – простое.

Теорема: Кольцо вычетов Zm – поле m – простое число. .

Док-во: нужно проверить, что каждый элемент является обратным, значит пусть Zm – поле, но m – составное, т.е. т.е. [a] и [b] – делители нуля, а в поле их нет. - по свойству поля. , но если Zm – поле, то m – не может быть составным.

Обратно: Пусть m – простое. Возьмем , но любой элемент имеет обратный, значит Zm – поле.

СМ.ПР

Решение сравнения в кольце целых чисел Zn.

Пусть - обозначение. Дано: Zn; [a][x]=[b]; ; Пусть - сравнение по модулю n, здесь решений бесконечное множество т.к. в Zn.

Теорема:

1. В Zn сравнение: имеет решение (a,n)|b

2. Если (a,n)|b, то сравнение имеет (a,n)=d различных по модулю n решений вида: - некоторое фиксированное решение.

Док-во:

1. 1. Прямое: Пусть есть решение ;

   2. Обратное: Пусть где - решение 1-го сравнения - решение 2-го сравнения. Покажем это: Пусть - решение 1-го сравнения , т.е. эти равенства эквивалентны. . Пусть , где - решение этого сравнения, т.к. - это решение и исходного сравнения.

2. , то - решение. Пусть есть еще решение: , а т.к. , т.е. при фиксированном l получаем d различных решений.

Пример1:

1. (a,6)=1 Пусть a=5;

2. 5U+6V=1; U=-1

Пример2: . Найти обратный к элементу [4]?

нет решений. Пусть есть решение. Пусть

Пример3: Сумма пересечений идеалов:

Пример4:

Пример5: 57, 24. Алгоритм Евклида:

U0=0

U1=-2

U2=U0-q2U1=0-2=-2

U3=U1-q3U2=-2-5=-7

V0=1

V1=-2

V2=V0-q2V1=1-2(-2)=5

V3=V1-q3V2=-2-5=-7

Пример6: 8,10,15 – их NOD в виде их линейной комбинации.

(6,10)=2; (2,15)=1 => (6,10,15)=1

или

U0=0

U1=1

U2=U0-q2U1=-1

V0=1

V1=-q1=-1

V2=V0-q2V1=1-1(-1)=2

2=(-1)10+2*6

Пример8: Кольцо .

Обратимые: Необратимые:

Найти обратные: ab=1; тоже обратим

Обратные образуют мультипликативную группу:

1. Замкнутость: a,b – обратимы

2. Ассоциативность выполняется для любых элементов в кольце.

3. и если а обратим , то , т.к. - обратим. G={1,5,7,11}

Пример9: Кольцо

47 – обратим. Построим обратный к 47 по умножению: есть решение.

3. - действительно обратим.

U0=0

U1=1

U2=U0-q2U1=0-11=-11

U3=U1-q3U2=1-1(-11)=12

V0=1

V1=-q1=-2

V2=V0-q2V1=1-11(-2)=23

V3=V1-q3V2=-2-1*23=-25

98U+47(-25)=1 ,

а

Пример10: - функция Эйлера.

Пример11: Найти все различные решения:

1. (63,333)|129 => решений нет

2. 1. 9|126 значит есть решение

Пример12:

1. 1. V0=1

   2. V1=-q1=-2

   3. V2=V0-q2V1=1-(-2)1=3

   4. V3=V1-q3V2=-2-1*3=-5

   5. V4=V2-q4V3=3-1(-5)=8

19,56,93,… a – решение т.к. (126,333)=9

Пример13: .

есть решение.

Находим обратное к 17. есть решение.

V0=1

V1=-3

V2=V0-q2V1=1-1(-3)=4

V3=V1-q3V2=-3-1*4=-7

[-7]=[-7+60k]=[53] => V3=53

Найти в интервале по mod60 , т.е.

Пример14:

1. g=(8,7,13)(1,4,6,5) hg=(1,3,13,15,9,5)(2,17,16,11,6,8,4,7,12,10)(14)

2. g=(8,7,13) hg(1,3,13,15,9,6,8)(2,17,16,11,4,7,12,10)(5)

k=NOK(7,8)=56

4