Б. М. ВЕРЕТЕННИКОВ
А. Б. ВЕРЕТЕННИКОВ
М. М. МИХАЛЕВА
АЛГЕБРА
И ТЕОРИЯ ЧИСЕЛ
Часть 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
Глава 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
3
Глава 1.
Первообразные корни в (Z/nZ)*
§ 1. Строение мультипликативной группы (Z/nZ)*
при простом n
Н
ачнем с замечания, что строение аддитивной группы
кольца Z /n Z очевидно. Это циклическая группа порядка n, и она порождена классом вычетов 1 = 1 + nZ.
Ответ на вопрос о строении группы (Z / n Z)* , т. е. группы обратимых элементов Z /n Z относительно кольцевого умножения, не является столь очевидным. Чтобы его получить, рассмотрим ряд утверждений.
Лемма 1.1. Пусть G — группа, a, b ОG , a = m, b = n и ab = ba.
mn
= НОК (m, n).
Тогда в G существует элемент порядка
(m, n)
Доказательство
При m | n или n | m утверждение леммы очевидно. Поэтому
считаем без ограничения общности, что n /| m и m /| n.
Предположим сначала, что m и n — взаимно простые числа.
Докажем, что элемент ab — искомый, т. е. ab = mn. Для этого обозначим ab = l . Тогда 1 = (ab)lm = a ml blm = blm , откуда n | lm и в силу
взаимной простоты n и m n | l . По симметрии m | ln, т. е. т | l .
4
§ 1. Строение мультипликативной группы (Z/nZ)* при простом n
Тогда опять в силу взаимной простоты m и n тn | l . Но очевидно, что (ab)mn = 1, откуда по свойству порядка элемента в группе имеем l | mn. Получаем в итоге l = mn, что и требовалось. Итак,
лемма доказана в случае взаимно простых m и n.
Пусть теперь m и n не взаимно простые. Ясно, что m и n можно представить в следующем виде:
m = p1e1 pses pse+s +11 prer , n = p1f1 psfs psf+s +11 prfr ,
где все pi — простые числа, попарно различные, и e1 і f1 ,,es і f s ,
es +1 < f s +1 ,, er < fr . Так как n /| m и m /| n , то s і1 и s < r .
m
f
e
e
f
e
e
Обозначим p11 ps s = m и ps +s +11 pr r = n . Тогда = ps +s +11 pr r
m
m
n
n
f
f
и = p1 1 ps s — взаимно простые числа. Элементы a = a m и b = b n
n
имеют взаимно простые порядки m и n, и по первой части доказательства леммы ab = mn . Но последнее число равно
НОК(m, n).
Лемма доказана.
Пример. Пусть G — группа, a, b ОG , a = 33 Ч 54 Ч 72 , b = 32 Ч 55 Ч 72 Ч11.
В соответствии с обозначениями выше m = 33 Ч 72 Ч 54 Ч110 ,
n = 32 Ч 7 Ч 55 Ч11, m = 33 Ч 72 , n = 55 Ч11.
Тогда a = a 625 , b = b 63 и a 625 Ч b 63 = НОК( a , b ) = 33 Ч 72 Ч 55 Ч11.
Теорема 1.1. Пусть F — конечное поле. Тогда мультипликативная группа F * = F \ {0} циклична.
Доказательство
Пусть a ОF * и порядок a в F * наибольший. Обозначим a = m.
Если m = F * , то теорема доказана. Если же m < F * , то любой
элемент из F * , порядок которого делит m, является корнем уравнения x m - 1 = 0, а так как число различных корней ненулевого
5
Глава 1. Первообразные корни в (Z/nZ)*
многочлена не превосходит его степени, то в F * существует элемент b, такой, что b /| m. По лемме в F * имеется элемент порядка НОК(m, b ) > m. Получили противоречие, которое доказывает теорему.
Следствие. Если p — простое число, то ( Z / pZ ) — циклическая группа порядка ( p - 1) .
*
Для нахождения порождающих ( Z / pZ ) классов вычетов
удобно использовать следующий результат.
*
a
a
Теорема 1.2. Пусть p — простое число и p - 1 = p1 1 ps s — разложение числа p -1 в произведение простых сомножителей.
Тогда если a
p -1
p1
є 1(mod p),, a
p -1
ps
є 1(mod p), то a = ( Z / pZ ) .
*
Доказательство
Докажем от противного. Предположим, что a = k < p -1
в ( Z / pZ ) . Тогда существует целое число j О [1, s ], такое, что
p -1
p -1
k
= kt для некоторого целого числа t
, откуда
pj
pj
*
иa
p -1
pj
= a kt = 1 в Z / pZ , что противоречит условию теоремы.
Теорема доказана.
Пример. Найдем порождающий класс вычетов в Z / 79Z. При
решении такого рода задач используют метод проб и ошибок
на базе теоремы 1.2.
Рассмотрим самый «простой» неединичный класс в Z / 79Z :
2 = 2 + 79Z.
Заметим, что 78 = 2 Ч 3 Ч13. Поэтому в соответствии с теоремой 1.2 надо посчитать в Z /79Z 26 , 2 26 , 239. Считаем: 26 = 64 № 1,
6
не порождающий класс. Значит, надо на роль порождающего
класса искать другой класс вычетов. Пробуем на эту роль класс
3 = 3 + 79Z.Считаем:3 2 = 9, 3 4 = 81 = 2, 38 = 4, 316 = 16, 332 = 19,
откуда 3 6 = 729 № 1, 3 26 = 316 +8+ 2 = 16 Ч 4 Ч 9 = 23 № 1, 339 = 332 + 4 + 2 +1 = 19 Ч 2 Ч 9 Ч 3 =
*
39
= 332 + 4 + 2 +1 = 19 Ч 2 Ч 9 Ч 3 = -1 № 1. Стало быть, 3 — порождающий ( Z / 79Z )
класс вычетов по теореме 1.2. Задача решена.
Для удобства речи используют следующее определение.
Определение 1.1. Класс a в Z /nZ называется первообразным
*
корнем по модулю n, если a порождает ( Z / nZ ) , т. е. порядок
класса a в ( Z / nZ ) равен j(n), где j — функция Эйлера.
Таким образом, 3 — первообразный корень по модулю 79,
а 2 — нет.
*
§ 2. Первообразные корни по модулю pm и 2pm
Теорема 1.3. Если p — нечетное простое число, то для любо-
го натурального m ( Z / p m Z ) – циклическая группа.
*
Доказательство
*
Поскольку ( Z / p m Z ) = j( p m ) = p m -1 Ч ( p - 1), то надо найти
класс вычетов в ( Z / p m Z ) , порядок которого равен p m-1 Ч ( p - 1).
*
Пусть a0 + pZ = ( Z / pZ ) . Такое число a0 существует в силу те*
m -1
оремы 1.1. Рассмотрим число a = a0p . Поскольку p m-1 взаимно
7
Глава 1. Первообразные корни в (Z/nZ)*
простое с ( p -1), то и a + pZ = ( Z / pZ ) ввиду известного свойm -1
m
ства циклической группы. Далееa p -1 = a0p ( p -1) = a0j( p ) є 1(mod p m ),
*
т. е. a + p m Z ( p - 1) в Z / p m Z, откуда с учетом того, что порядок a
по модулю p равен в точности ( p -1), заключаем, что и порядок
a + p m Z в Z / p m Z равен ( p -1).
Докажем теперь, что класс 1 + p в ( Z / p m Z ) имеет порядок
*
p m-1 .
По формуле бинома Ньютона имеем
p
(1 + p) p = еC pi pi = 1 + p 2 + C p2 p 2 + + p p ,
i =0
откуда заключаем, что (1 + p) p є (1 + p 2 )(mod p3 ). Докажем по индукции, что для любого натурального числа j
j
(1 + p) p є (1 + p j +1 )(mod p j + 2 ). В самом деле, предположим, что
данное равенство имеет место при фиксированном j. Тогда
j +1
j
(1 + p) p = (1 + p) p Ч p = (1 + p j +1 + sp j + 2 ) p = (1 + (1 + sp) p j +1 ) p для некоторого целого числа s. Продолжая, получим
(1 + p) p
j +1
p
= еC pi (1 + sp)i p( j +1)i = 1 + p j + 2 (1 + sp) + C p2 (1 + sp)2 p 2( j +1) + +
i =0
+(1 + sp) p p( j +1) p є (1 + p j + 2 )(mod p j +3 ).
Таким образом, шаг индукции сделан и рассматриваемое
m -1
сравнение доказано. При j = m -1 получим (1 + p) p є 1(mod p m ).
*
m -2
Однако (1 + p) p є (1 + p m -1 )(mod p m ), откуда в Z / p m Z
1 + p = p m -1 . Ввиду взаимной простоты чисел p m-1 и p -1 по пер-
(
)
вой части доказательства леммы 1.1 имеем, что 1 + p Ч a = p m -1 ( p - 1).
Теорема доказана.
Пример. Найдем первообразный корень по модулю 125, используя рассуждения в доказательстве теоремы.
8
§ 2. Первообразные корни по модулю pm и 2pm
Ясно, что a0 = 2 = 2 + 5Z — первообразный корень по моду2
лю 5. Посчитаем 2(5 ) по модулю 125. Имеем в Z /125Z
2 2 = 4, 2 4 = 16, 28 = 256 = 6, 216 = 36 , о т к у д а 2 25 = 216 +8+1 = 36 Ч 6 Ч 2 = 5
2 25 = 216 +8+1 = 36 Ч 6 Ч 2 = 57. Тогда 57 Ч 6 = 342 = 92 — первообразный корень
по модулю 125. Заметим, что в процессе решения данной задачи мы нашли также класс вычетов, а именно 57, порядок которого Z /125Z равен 4 = p - 1, где p = 5.
В следующих четырех теоремах рассматривается подход
к первообразным корням по модулю p m . Расширим сначала область применения термина «первообразный корень».
Определение 1.2. Число a — первообразный корень по моду*
лю n, если a = ( Z / n Z ) .
Из контекста всегда бывает ясно, что понимается под первообразным корнем — число или соответствующий класс вычетов.
Теорема 1.4. Любой первообразный корень по модулю p m
(m і1, р — простое) является также первообразным корнем
по модулю p n при любом натуральном n < m, в частности по модулю p.
Доказательство
Легко понять, что отображение j : Z / p m Z ® Z / p n Z, задаваемое формулой j(a + p m Z) = a + p n Z для любого a ОZ, правильно
определено и является сюръективным кольцевым гомоморфизмом, индуцирующим сюръективный групповой гомоморфизм
*
*
*
j* : ( Z / p m Z ) ® ( Z / p n Z ) . Поэтому если a + p m Z = ( Z / p m Z ) ,
то a + p n Z = ( Z / p n Z ) .
*
Теорема доказана.
Из теоремы 1.4 вытекает, что первообразный корень по модулю p m можно искать среди первообразных корней по модулю p.
9
Глава 1. Первообразные корни в (Z/nZ)*
Теорема 1.5. Если a — первообразный корень по модулю проm- 2
стого числа p и a p ( p -1) є 1(mod p m ), где m і 2, то a также и первообразный корень по модулю p m .
Доказательство
*
Пусть k — порядок класса a + p m Z в ( Z / p m Z ) . Тогда по теореме Лагранжа из теории групп k | j( p m ), т. е. k | p m -1 ( p - 1). Так
как a k є 1(mod p) и порядок класса a + pZ в Z / p Z равен ( p -1)
по условию, то ( p -1) | k . Тогда k = p g ( p - 1), где 0 Ј g Ј m - 1, и если
m - 2 ( p -1 )
g < m - 1, то a p
є 1(mod p m ), что противоречит условию теоремы. Следовательно, k = j( p m ).
Теорема доказана.
Теорема 1.6. Если a — первообразный корень по модулю
нечетного простого p, то из двух чисел a и a+p хотя бы одно является первообразным корнем по модулю p 2 .
Доказательство
Предположим, что ни a, ни a + p не являются первообразными корнями по модулю p m .
Тогда по теореме 1.5 a p-1 є 1(mod p 2 ) и (a + p) p -1 є 1(mod p 2 ),
p -1
откуда (a + p) p -1 - a p -1 = ( p - 1)a p - 2 p + еC pj -1a p -1- j p j є 0(mod p 2 ).
j =2
Но тогда p | ( p - 1)a , что противоречиво, ибо a взаимно просто с p.
Теорема доказана.
p-2
Пример. Найдем первообразные корни по модулям 49 и 121.
Очевидно, что 3 — первообразный корень по модулю 7, т. к.
*
2
3 є 1(mod 7) и 33 є 1(mod 7), а ( Z / 7Z ) = 6. Далее: 3 6 = 729 = 43 = 1
3 6 = 729 = 43 = 1 в Z / 49Z. Следовательно, 3 — первообразный корень
по модулю 49 по теореме 1.5.
10
§ 2. Первообразные корни по модулю pm и 2pm
Так как в Z /11Z 2 2 № 1 и 25 № 1, а ( Z / 11Z ) = 10, то 2 — перво*
образный корень по модулю 11. Далее: 210 = 1024 є 1(mod 121),
откуда 2 — первообразный корень по модулю 121 по теореме 1.5.
Лемма 1.2. Для любого a ОR и для любого целого d при a > 0,
й [a ] щ й a щ
d > 0 имеет место равенство к ъ = к ъ .
кл d ъы л d ы
Доказательство
Обозначим [a ] = n. Тогда a = n + s, 0 Ј s < 1. Требуется доказать,
йn + s щ й n щ
что к
ъ = к ъ.
л d ы лd ы
Поделим n на d с остатком: n = dq + r , 0 Ј r Ј d - 1. Тогда
n
+
sщ й
r sщ
r +s
й
к d ъ = кq + d + d ъ = q, т. к. d 1, где n = p1 1 pk k ,
(Z / n Z)* изоморфна прямому произведению групп Z / p mi Z. Первообразный корень по модулю n >1 существует тогда и только
тогда, когда n имеет вид p m , 2 p m , p — нечетное простое, или n = 2
или 4.
Доказательство
Первая часть доказательства проведена выше. Если
n = 2m q, m і 3, q нечетное, то по теореме 1.10 (Z / n Z)* имеет нециклическую 2‑подгруппу, следовательно, (Z / n Z)* нециклична
и первообразных корней по модулю n не существует. Если n = 4q,
m
m
где q нечетное, или n = p1 1 p2 2 M , где p1 , p2 — различные простые
числа и m1 , m2 і 1, то в первом случае (Z / n Z)* (Z / 4 Z)* ґ (Z /q Z)* ,
m
m
а во втором (Z / n Z)* (Z / p1 1 Z)* ґ (Z / p2 2 Z)* ґ (Z / M Z)* , и в обоих случаях в (Z / n Z)* имеется как минимум три инволюции, откуда (Z / n Z)* не циклична.
Теорема доказана.
17
Глава 2.
Закон взаимности Гаусса
§ 1. Символ Лежандра и закон взаимности Гаусса
Определение 2.1. Элемент a кольца R — квадрат, если существует элемент b из R, такой, что b 2 = a.
В противном случае называем a неквадратом.
Определение 2.2. Пусть p — нечетное простое число,
a О(Z / p Z)* . Тогда символ Лежандра класса a по модулю p обожaц
значается з ч и равен 1, если a — квадрат в Z / p Z, и равен (-1),
и pш
ж0ц
если a — неквадрат в Z / p Z. Считаем также, что з ч = 0.
и pш
Определение 2.3. Для любого целого числа x, не делящегося
жxц
жxц
на p ( p > 2), символ Лежандра з ч равен з ч , где x = x + pZ.
и pш
и pш
В дальнейшем p всегда означает нечетное простое число.
Лемма 2.1. Пусть x — целое число. Тогда если x = x + pZ,
p -1
жxц
то з ч = x 2 , где слева тоже стоит класс вычетов по модулю p.
и pш
18
§ 1. Символ Лежандра и закон взаимности Гаусса
Доказательство
жxц
Пусть сначала з ч = 1. Тогда в силу нечетности p имеем
и pш
жxц
2s
з ч = 1, откуда x — квадрат Z / p Z, т. е. x = w для некоторого наи pш
турального s, где w — первообразный корень по модулю p. Тогp -1
жxц
да x 2 = w( p -1)s = 1, так что при з ч = 1 все доказано.
и pш
жxц
жxц
Пусть теперь з ч = -1. Тогда з ч = -1 и x — неквадрат
и pш
и pш
2 k +1
в Z / p Z, т. е. x = w
для некоторого целого k. Далее имеем
x
p -1
2
( 2 k +1)
=w
p -1
2
= wk ( p -1) w
p -1
2
=w
p -1
2
. Так как w
p-1
2
= 2 и в цикличе-
{
}
ской группе w ровно одна циклическая подгруппа 1, -1 ,
p-1
2
то w = -1.
Лемма доказана.
Заметим, что доказанную лемму иногда называют критерием Эйлера.
ж 5ц
Пример 1. Посчитаем символ Лежандра з ч . Имеем 5 2 = 25 = 8
и 17 ш
p-1
в Z /17 Z, 5 4 = 64 = -4, 58 = 16 = -1, а 58 — это как раз 5 2 , где p = 17.
ж 5ц
Так что з ч = -1, в частности 5 — неквадрат в Z /17 Z.
и 17 ш
ж 13 ц
Пример 2. Посчитаем символ Лежандра з ч . Имеем при
и 41 ш
2
p -1
p = 41, что
= 20 = 16 + 4. Далее считаем: 13 = 169 = 5 в Z / 41 Z,
2
19
Глава 2. Закон взаимности Гаусса
4
13 = 25 = -16,
8
13 = 256 = 10,
20
16
13 = 100 = 18.
Тогда
13 = 18 Ч (-16) = -288 = -1, так что по критерию Эйлера снова име-
ем, что 13 — неквадрат в Z / 41 Z.
Лемма 2.2. Отображение f : Z ® {-1,1, 0}, такое, что для люжxц
бого целого x f ( x ) = з ч , является гомоморфизмом полугрупп
и pш
Z и {-1,1, 0}, рассматриваемых относительно обычного умноже-
ния чисел.
Доказательство
Используя критерий Эйлера (лемма 2.1), имеем для любых
p -1 p -1
p -1
ж xy ц
целых x, y : f ( xy ) = з ч = ( xy ) 2 = x 2 y 2 = f ( x ) f ( y ), откуда
и p ш
следует справедливость доказываемого утверждения.
Заметим, что леммой 2.2 часто приходится пользоваться при
практических вычислениях символа Лежандра.
Перед теоремой 2.1 — так называемым дополнением к закону
взаимности Гаусса — докажем следующую любопытную лемму.
Лемма 2.3 (лемма Гаусса). Пусть S — такое подмножество
в F p* , что F p* = S И (-S ) и S З (-S ) = Ж. Для любого s из S и любого a из F p* определим es (a) из равенства as = es (a)sa , где sa О S
жaц
и es (a) О{-1,1}. Тогда имеет место формула з ч = Х es (a).
и p ш sОS
Доказательство
Предположим сначала, что s, s ў О S , s № s ў, но sa = saў . Тогда
из равенств as = es (a)sa , as ў = es ў (a)sa следует, что s = es (a)sa a -1 ,
s ў = es ў (a)sa a -1, т. е. s = - s ў, что противоречит условию леммы. Этим
доказано, что отображение s ® sa — это биекция S на себя. Да20
§ 1. Символ Лежандра и закон взаимности Гаусса
лее имеем
Х as = Х es (a)sa , откуда a
sОS
sОS
и в силу замечания выше получаемa
p -1
2
p -1
2
ж
ц
Х s = зи Х e (a) чш Х s ,
sОS
sОS
s
sОS
a
жaц
= Х es (a), т. е. з ч = Х es (a)
sОS
и p ш sОS
на основании леммы 2.1.
Лемма доказана.
ж 7ц
Пример. Пользуясь леммой Гаусса, посчитаем з ч . В роли
и 19 ш
p -1
. В нашем слуS в (Z / p Z)* обычно берется множество 1, 2
2
чае S = 1, 2, 9 . Имеем:
{
}
7 Ч 1 = 7;
7 Ч 2 = 14 = -5;
7 Ч 3 = 21 = 2;
7 Ч 4 = 28 = 9;
7 Ч 5 = 35 = -3;
7 Ч 6 = 42 = 4;
7 Ч 7 = 49 = -8;
7 Ч 8 = 56 = -1;
7 Ч 9 = 63 = 6.
ж 7ц
Тогда по лемме Гаусса з ч = (-1)4 = 1 (4 — число минусов
и 19 ш
в последней колонке в равенствах выше). Заметим, что только
перебором можно установить, что 7 = 8 2.
Теорема 2.1 (дополнение к закону взаимности Гаусса). Справедливы формулы:
ж1ц
а) з ч = 1;
и pш
21
Глава 2. Закон взаимности Гаусса
ж -1 ц м1 при p є 1(mod 4),
б) з ч = н
и p ш о-1 при p є -1(mod 4);
ж 2 ц м1 при p є ±1(mod 8),
в) з ч = н
и p ш о-1 при p є ±5(mod 8).
Доказательство
Отметим сначала, что (а) очевидно, т. к. 1 = 1 2. Докажем пункт (б).
4 k +1
ж -1 ц
По лемме 2.1 имеем при p = 4k + 1, что з ч = (-1) 2 = (-1)2k = 1,
и p ш
-2 + 4 k
ж -1 ц
а при p = -1 + 4k имеем з ч = (-1) 2 = (-1)2k -1 = -1, так что (б)
и p ш
доказано.
Для доказательства пункта (в) воспользуемся леммой Гаусp - 1 ьп
p -1
пм
са и в роли S возьмем н1, 2,
э . Ясно, что es (2) = 1 при s Ј
2 юп
4
оп
p -1
p -1
Последние комментарии
16 часов 34 минут назад
21 часов 37 минут назад
1 день 5 часов назад
1 день 7 часов назад
1 день 8 часов назад
2 дней 19 часов назад