Алгебра и теория чисел. В двух частях. Часть 2
Покупка
Издательство:
Издательство Уральского университета
Год издания: 2019
Кол-во страниц: 72
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-7996-2568-9
Артикул: 800376.01.99
Учебное пособие включает в себя следующие разделы курса «Алгебра и теория чисел»: строение мультипликативной группы (Z/«Z)*, символ Лежандра и символ Якоби, алгебратические числа. Содержит индивидуальные домашние задания. Предназначено для студентов института радиоэлектроники и информационных технологий — РТФ.
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Министерство науки и высшего образования Российской Федерации Уральский федеральный университет имени первого Президента России Б. Н. Ельцина Б. М. Веретенников, А. Б. Веретенников, М. М. Михалева АЛГЕБРА И ТЕОРИЯ ЧИСЕЛ Учебное пособие В двух частях Часть 2 Рекомендовано методическим советом Уральского федерального университета для студентов, обучающихся по направлению подготовки 02.03.03 — Математическое обеспечение и администрирование информационных систем Екатеринбург Издательство Уральского университета 2019
УДК 511/512(075.8)
ББК 22.13я73+22.14я73
В31
Рецензенты:
кафедра прикладной математики Уральского государственного экономического университета (зав. кафедрой канд. физ.-мат. наук, доц.
Ю. Б. Мельников);
канд. физ.-мат. наук, ст. науч. сотр. Института математики и механики УрО РАН И. Н. Белоусов
Научный редактор — канд. физ.-мат. наук, доц. Н. В. Чуксина
Веретенников, Б. М.
В31 Алгебра и теория чисел : учеб. пособие. В 2 ч. Ч. 2 / Б. М. Веретенников, А. Б. Веретенников, М. М. Михалева. — Екатеринбург :
Изд-во Урал. ун-та, 2019. — 72 с.
ISBN 978-5-7996-2568-9 (ч. 2)
ISBN 978-5-7996-1166-8
Учебное пособие включает в себя следующие разделы курса «Алгебра
и теория чисел»: строение мультипликативной группы (
/
) ,
*
n
символ
Лежандра и символ Якоби, алгебраические числа. Содержит индивидуальные домашние задания. Предназначено для студентов института радиоэлектроники и информационных технологий — РТФ.
Библиогр.: 9 назв.
УДК 511/512(075.8)
ББК 22.13я73+22.14я73
ISBN 978-5-7996-2568-9 (ч. 2)
© Уральский федеральный
ISBN 978-5-7996-1166-8
университет, 2019
Оглавление
Глава 1. Первообразные корни в (Z/nZ)*...........................4
§ 1. Строение мультипликативной
группы (Z/nZ)* при простом n...................................4
§ 2. Первообразные корни по модулю pm и 2pm................7
§ 3. Строение (Z/nZ)* в общем случае............................16
Глава 2. Закон взаимности Гаусса....................................18
§ 1. Символ Лежандра и закон взаимности Гаусса........18
§ 2. Символ Якоби...........................................................30
Глава 3. Алгебраические числа.........................................36
Индивидуальные домашние задания................................45
Библиографический список..............................................70
Глава 1. Первообразные корни в (Z/nZ)* § 1. Строение мультипликативной группы (Z/nZ)* при простом n Н ачнем с замечания, что строение аддитивной группы кольца Z Z /n очевидно. Это циклическая группа порядка n, и она порождена классом вычетов 1 1 = +nZ. Ответ на вопрос о строении группы ( / ) , * Z Z n т. е. группы обратимых элементов Z Z /n относительно кольцевого умножения, не является столь очевидным. Чтобы его получить, рассмотрим ряд утверждений. Лемма 1.1. Пусть G — группа, a b G , , О a m = , b n = и ab ba = . Тогда в G существует элемент порядка mn m n m n ( , ) ( , ). = НОК Доказательство При m n | или n m | утверждение леммы очевидно. Поэтому считаем без ограничения общности, что n m /| и m n /| . Предположим сначала, что m и n — взаимно простые числа. Докажем, что элемент ab — искомый, т. е. ab mn = . Для этого обозначим ab l = . Тогда 1= = = ( ) , ab a b b lm ml lm lm откуда n lm | и в силу взаимной простоты n и m n l| . По симметрии m ln | , т. е. т l| .
§ 1. Строение мультипликативной группы (Z/nZ)* при простом n
Тогда опять в силу взаимной простоты m и n тn l| . Но очевидно, что (
)
,
ab mn =1 откуда по свойству порядка элемента в группе имеем l mn
|
. Получаем в итоге l
mn
=
, что и требовалось. Итак,
лемма доказана в случае взаимно простых m и n.
Пусть теперь m и n не взаимно простые. Ясно, что m и n можно представить в следующем виде:
m
p
p
p
p
e
s
e
s
e
r
e
s
s
r
=
+
+
1
1
1
1
, n
p
p
p
p
f
s
f
s
f
r
f
s
s
r
=
+
+
1
1
1
1
,
где все pi — простые числа, попарно различные, и e
f
1
1
і
,,e
f
s
s
і
,
e
f
e
f
s
s
r
r
+
+
<
1
1,
,
.
<
Так как n m
/|
и m n
/|
, то s і1 и s
r
< .
Обозначим p
p
m
e
s
es
1
1
=
и p
p
n
s
f
r
f
s
r
+
+
=
1
1
. Тогда m
m
p
p
s
e
r
e
s
r
=
+
+
1
1
и n
n
p
p
f
s
fs
=
1
1
— взаимно простые числа. Элементы a
a
m
m
=
и b
b
n
n
=
имеют взаимно простые порядки m и n, и по первой части доказательства леммы ab
mn
=
. Но последнее число равно
НОК( , ).
m n
Лемма доказана.
Пример. Пусть G — группа, a b G
,
,
О
a =
Ч
Ч
3
5
7
3
4
2, b =
Ч
Ч
Ч
3
5
7
11
2
5
2
.
В соответствии с обозначениями выше m =
Ч
Ч
Ч
3
7
5
11
3
2
4
0,
n =
Ч Ч
Ч
3
7 5 11
2
5
, m =
Ч
3
7
3
2, n =
Ч
5 11
5
.
Тогда a
a
=
625, b
b
=
63 и a
b
a b
625
63
3
2
5
3
7
5 11
Ч
=
=
Ч
Ч
Ч
НОК(
,
)
.
Теорема 1.1. Пусть F — конечное поле. Тогда мультипликативная группа F
F
*
\
=
{ }
0 циклична.
Доказательство
Пусть aОF * и порядок a в F * наибольший. Обозначим a = m.
Если m
F
=
* , то теорема доказана. Если же m
F
<
* , то любой
элемент из F *, порядок которого делит m, является корнем уравнения xm - =
1
0, а так как число различных корней ненулевого
Глава 1. Первообразные корни в (Z/nZ)* многочлена не превосходит его степени, то в F * существует элемент b, такой, что b /| . m По лемме в F * имеется элемент порядка НОК( , ) . m m b > Получили противоречие, которое доказывает теорему. Следствие. Если p — простое число, то Z Z / * p ( ) — циклическая группа порядка p - ( ) 1 . Для нахождения порождающих Z Z / * p ( ) классов вычетов удобно использовать следующий результат. Теорема 1.2. Пусть p — простое число и p p ps s - = 1 1 1 a a — разложение числа p -1 в произведение простых сомножителей. Тогда если a p a p p p p ps - - є є 1 1 1 1 1 (mod ), , (mod ), то a p = ( ) Z Z / . * Доказательство Докажем от противного. Предположим, что a k p = < -1 в Z Z / . * p ( ) Тогда существует целое число j s О[ ] 1, , такое, что k p pj -1, откуда p p kt j - = 1 для некоторого целого числа t и a a p p kt j - = = 1 1 в Z Z / p , что противоречит условию теоремы. Теорема доказана. Пример. Найдем порождающий класс вычетов в Z Z / . 79 При решении такого рода задач используют метод проб и ошибок на базе теоремы 1.2. Рассмотрим самый «простой» неединичный класс в Z Z / : 79 2 2 79 = + Z. Заметим, что 78 2 3 13 = Ч Ч . Поэтому в соответствии с теоремой 1.2 надо посчитать в Z Z /79 2 2 2 6 26 39 , , . Считаем: 2 64 1 6 = №,
§ 2. Первообразные корни по модулю pm и 2pm 26 16 8 2 = + + , 2 2 39 32 4 2 1 = + + + . Далее имеем: 2 4 2 = , 2 16 4 = , 2 256 19 8 = = , 2 361 45 16 = = , 2 2025 50 32 = = , откуда 2 45 19 4 45 2 26 = Ч Ч = Ч - ( ) = 90 1 = - №, 2 50 16 4 2 6400 1 39 = Ч Ч Ч = = . Получим, что 2 78 < , т. е. 2 — не порождающий класс. Значит, надо на роль порождающего класса искать другой класс вычетов. Пробуем на эту роль класс 3 3 79 = + Z. Считаем: 3 9 3 81 2 3 4 3 16 3 19 2 4 8 16 32 = = = = = = , , , , , откуда 3 729 1 6 = №, 3 3 16 4 9 23 1 26 16 8 2 = = Ч Ч = № + + , 3 3 39 32 4 2 1 = = + + + 19 2 9 3 1 1 = Ч Ч Ч = - №. Стало быть, 3 — порождающий Z Z / * 79 ( ) класс вычетов по теореме 1.2. Задача решена. Для удобства речи используют следующее определение. Определение 1.1. Класс a в Z Z /n называется первообразным корнем по модулю n, если a порождает Z Z / , * n ( ) т. е. порядок класса a в Z Z / * n ( ) равен j( ), n где j — функция Эйлера. Таким образом, 3 — первообразный корень по модулю 79, а 2 — нет. § 2. Первообразные корни по модулю pm и 2pm Теорема 1.3. Если p — нечетное простое число, то для любого натурального m Z Z / * pm ( ) – циклическая группа. Доказательство Поскольку Z Z / ( ) ( ), * p p p p m m m ( ) = = Ч - - j 1 1 то надо найти класс вычетов в Z Z / , * pm ( ) порядок которого равен p p m- Ч - 1 1 ( ). Пусть a p p 0 + = ( ) Z Z Z / . * Такое число a0 существует в силу теоремы 1.1. Рассмотрим число a a pm = - 0 1. Поскольку pm-1 взаимно
Глава 1. Первообразные корни в (Z/nZ)* простое с ( ), p -1 то и a p p + = ( ) Z Z Z / * ввиду известного свойства циклической группы. Далее a a a p p p p p m m m - - = = є - 1 0 1 0 1 1 ( ) ( ) (mod ), j т. е. a p p m + - Z ( ) 1 в Z Z / , pm откуда с учетом того, что порядок a по модулю p равен в точности ( ), p -1 заключаем, что и порядок a pm + Z в Z Z / pm равен ( ). p -1 Докажем теперь, что класс 1+ p в Z Z / * pm ( ) имеет порядок pm-1. По формуле бинома Ньютона имеем ( ) , 1 1 2 2 2 0 + = = + + + + =е p C p p C p p p p i i p p i p откуда заключаем, что ( ) ( )(mod ). 1 1 2 3 + є + p p p p Докажем по индукции, что для любого натурального числа j ( ) ( )(mod ). 1 1 1 2 + є + + + p p p p j j j В самом деле, предположим, что данное равенство имеет место при фиксированном j. Тогда ( ) ( ) ( ) ( ( ) ) 1 1 1 1 1 1 1 2 1 + = + = + + = + + + Ч + + + p p p sp sp p p p p j j p j p j j для некоторого целого числа s. Продолжая, получим ( ) ( ) ( ) ( ) ( ) ( ) 1 1 1 1 1 1 1 2 2 2 2 1 + = + = + + + + + + + + p C sp p p sp C sp p p p i i j i j p j j + + + + є + = + + + е i p p j p j j sp p p p 0 1 2 3 1 1 ( ) ( )(mod ). ( ) Таким образом, шаг индукции сделан и рассматриваемое сравнение доказано. При j m = -1 получим ( ) (mod ). 1 1 1 + є - p p p m m Однако ( ) ( )(mod ), 1 1 2 1 + є + - - p p p p m m m откуда в Z Z / * pm ( ) 1 1 + = - p pm . Ввиду взаимной простоты чисел pm-1 и p -1 по первой части доказательства леммы 1.1 имеем, что 1 1 1 + Ч = - - p a p p m ( ). Теорема доказана. Пример. Найдем первообразный корень по модулю 125, используя рассуждения в доказательстве теоремы.