Алгебра и теория чисел. В двух частях. Часть 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, ис-
пользуя рассуждения в доказательстве теоремы.

§ 2. Первообразные корни по модулю pm и 2pm

Ясно, что a0
2
2
5
=
=
+ Z — первообразный корень по моду-

лю 5. Посчитаем 2 52
(
) по модулю 125. Имеем в Z
Z
/125  

2
4
2
16
2
256
6
2
36
2
4
8
16
=
=
=
=
=
,
,
,
, 
откуда 
2
2
36 6 2
5
25
16 8 1
=
=
Ч Ч
=
+ +
 

2
2
36 6 2
57
25
16 8 1
=
=
Ч Ч
=
+ +
. Тогда 57 6
342
92
Ч
=
=
 — первообразный корень 
по модулю 125. Заметим, что в процессе решения данной зада-
чи мы нашли также класс вычетов, а именно 57, порядок кото-
рого Z
Z
/125  равен 4
1
=
-
p
, где p = 5.

В следующих четырех теоремах рассматривается подход 
к первообразным корням по модулю pm. Расширим сначала об-
ласть применения термина «первообразный корень».

Определение 1.2. Число a — первообразный корень по моду-
лю n, если a
n
= (
)
Z
Z
/
.
*

Из контекста всегда бывает ясно, что понимается под перво-
образным корнем — число или соответствующий класс вычетов.

Теорема 1.4. Любой первообразный корень по модулю pm 

(
,
m і1  р — простое) является также первообразным корнем 
по модулю pn при любом натуральном n
m
<
, в частности по мо-
дулю p.
Доказательство
Легко понять, что отображение j:
/
/
,
Z
Z
Z
Z
p
p
m
n
®
 задава-
емое формулой j(
)
a
p
a
p
m
n
+
=
+
Z
Z для любого aОZ, правильно 
определено и является сюръективным кольцевым гомоморфиз-
мом, индуцирующим сюръективный групповой гомоморфизм 
j*
*
*
:
/
/
.
Z
Z
Z
Z
p
p
m
n
(
) ®(
)  Поэтому если a
p
p
m
m
+
=(
)
Z
Z
Z
/
,
*  

то a
p
p
n
n
+
=(
)
Z
Z
Z
/
.
*

Теорема доказана.
Из теоремы 1.4 вытекает, что первообразный корень по моду-
лю pm можно искать среди первообразных корней по модулю p.

Глава 1. Первообразные корни в (Z/nZ)*

Теорема 1.5. Если a — первообразный корень по модулю про-
стого числа p и a
p
p
p
m
m-
-
є

2
1
1
(
)
(mod
), где m і 2, то a также и пер-
вообразный корень по модулю pm.

Доказательство
Пусть k — порядок класса a
pm
+
Z в Z
Z
/
.
*
pm
(
)  Тогда по тео-

реме Лагранжа из теории групп k
pm
| (
),
j
 т. е. k p
p
m
|
(
).
-
-
1
1  Так 
как a
p
k є1(mod ) и порядок класса a
p
+ Z в Z
Z
/ p  равен (
)
p -1  
по условию, то (
)| .
p
k
-1
 Тогда k
p
p
=
-
g(
),
1  где 0
1
Ј
Ј
-
g
m
, и если 

g <
-
m 1, то a
p
p
m
m
p
-
- є

2
1
1

(
)
(mod
), что противоречит условию тео-
ремы. Следовательно, k
pm
= j(
).

Теорема доказана.

Теорема 1.6. Если a — первообразный корень по модулю 
нечетного простого p, то из двух чисел a и a+p хотя бы одно яв-
ляется первообразным корнем по модулю p2.

Доказательство
Предположим, что ни a, ни a + p не являются первообразны-
ми корнями по модулю pm. 
Тогда по теореме 1.5 a
p
p- є
1
2
1(mod
) и (
)
(mod
),
a
p
p
p
+
є
-1
2
1
 

откуда (
)
(
)
(mod
).
a
p
a
p
a
p
C
a
p
p
p
p
p
p
j
p
j
j

j

p

+
-
=
-
+
є
-
-
-
-
- -

=

-
е
1
1
2
1

1
2

2

1
1
0
 

Но тогда p
p
a p
|(
)
,
-
-
1
2  что противоречиво, ибо a взаимно про-
сто с p.
Теорема доказана.

Пример. Найдем первообразные корни по модулям 49 и 121.
Очевидно, что 3 — первообразный корень по модулю 7, т. к. 

3
1
7
2 є (mod ) и 3
1
7
3 є (mod ), а Z
Z
/
.
*
7
6
(
) =
 Далее: 3
729
43
1
6 =
=
=
 

3
729
43
1
6 =
=
=
 в Z
Z
/
.
49
 Следовательно, 3 — первообразный корень 
по модулю 49 по теореме 1.5.

§ 2. Первообразные корни по модулю pm и 2pm

Так как в Z
Z
/11  2
1
2 №  и 2
1
5 № , а Z
Z
/
,
*
11
10
(
) =
 то 2 — перво-

образный корень по модулю 11. Далее: 2
1024
1
121
10 =
є (mod
), 
откуда 2 — первообразный корень по модулю 121 по теореме 1.5.

Лемма 1.2. Для любого aОR и для любого целого d при a > 0, 

d > 0 имеет место равенство 

a
a
[ ]
й

л
к
к

щ

ы
ъ
ъ

= й
лк
щ
ыъ
d
d .

Доказательство
Обозначим a
[ ] = n. Тогда a =
+
n
s, 0
1
Ј
<
s
. Требуется доказать, 

что n
s
d
n
d
+
й
лк
щ
ыъ = й
лк

щ
ыъ.

Поделим n на d с остатком: n
dq
r
=
+ , 0
1
Ј
Ј
-
r
d
. Тогда 

n
s
d
q
r
d
s
d
q
+
й
лк
щ
ыъ =
+
+
й
лк

щ
ыъ = , т. к. r
s
d
+
<1 ввиду указанных выше нера-

венств для s и r. Но q — это как раз n
d
й
лк
щ
ыъ.

Лемма доказана.

Теорема 1.7. Пусть p — простое число, n — натуральное, a — 
наибольшее целое неотрицательное со свойством p n
a
!. Тогда 

a = й

лк

щ

ыъ + й

лк

щ

ыъ + й

лк

щ

ыъ +
n
p

n
p

n
p
2
3
 (сумма справа конечна, т. к. при всех до-

статочно больших натуральных k имеем n

pk

й

лк
щ

ыъ = 0).

Доказательство
Докажем индукцией по n. Ясно, что при n =1 теорема спра-
ведлива. Предположим, что теорема верна при всех n с услови-
ем 1Ј
<
n
N, где N — фиксированное натуральное число боль-
ше 1, и докажем, что она верна при n
N
=
.