Алгебра и теория чисел. В двух частях. Часть 2

Министерство науки и высшего образования  
Российской Федерации
Уральский федеральный университет
имени первого Президента России Б. Н. Ельцина

Б. М. Веретенников, А. Б. Веретенников, М. М. Михалева

АЛГЕБРА 
И ТЕОРИЯ ЧИСЕЛ

Учебное пособие

В двух частях
Часть 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

2
2
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
90
1
26 =
Ч
Ч
=
Ч (
) = № ,
 

4
45
2
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
19 2 9 3
39
32 4 2 1
=
=
Ч Ч Ч
=
+ + +
 

3
19 2 9 3
1
1
39
32 4 2 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, используя рассуждения в доказательстве теоремы.