Ю.И. Журавлёв, Ю.А. Флёров, М.Н. Вялый - Дискретный анализ. Основы высшей алгебры (1127101), страница 28
Текст из файла (страница 28)
Тогда v · {x}, v · {x2 }, . . . — циклические сдвиги, т. е. также принадлежат I. Значит, v · {u} ∈ Iдля любого многочлена u. Поэтому I — идеал.Разложим многочлен xn − 1 на неприводимые над GF (p)множители:xn − 1 = f1a1 (x)f2a2 (x) . . . fsas (x).По китайской теореме об остатках кольцо классов вычетов помодулю многочлена xn − 1 изоморфно прямой сумме колец3.9.Циклические подпространства163классов вычетов по модулю многочленов fiai (x). Иногда такое разложение оказывается полезным.
Поэтому рассмотримзадачу разложения xn − 1 на неприводимые множители.Мы показали в разделе 3.7, что любой многочлен с коэффициентами из GF (p) разлагается в некотором конечном полехарактеристики p на линейные множители. Пусть GF (q) — поле характеристики p, в котором многочлен xn − 1 разлагаетсяна линейные множители. Поскольку в поле характеристики pвыполняется равенство xkp − 1 = (xk − 1)p , интересен случай,когда n взаимно просто с p. В этом случае у многочлена xn − 1кратных корней нет, так как он взаимно прост со своей производной nxn−1 .Равенство xn = 1 означает, что порядок элемента x в мультипликативной группе поля GF (q) делит n. Мультипликативная группа конечного поля циклична (теорема 3.44).
Корниуравнения xn −1 = 0 образуют подгруппу этой группы (группакорней из единицы степени n), и эта подгруппа также циклическая. Ее порождающие элементы называются примитивнымикорнями степени n.Подгруппа порядка n в циклической группе существуеттогда и только тогда, когда n делит порядок циклическойгруппы. Таким образом, мы получаем необходимое и достаточное условие того, что поле GF (q) содержит группу корнейиз единицы степени n: n должно быть делителем q − 1.Чтобы вернуться от разложения xn −1 на линейные множители в поле GF (q) к разложению на неприводимые множителив поле GF (p), нужно понять, какие корни из единицы будутвходить в неприводимый делитель f (x).
Как мы уже установили (теорема 3.41), если уравнение f (x) = 0 имеет корень β,2то и β p , β p и т. д. также будут корнями f (x). Таким образом,количество и степени неприводимых делителей xn − 1 можнонайти, разбив вычеты по модулю n на орбиты отображенияt 7→ pt mod n.Пример 3.55. Рассмотрим еще раз разложение многочленаx15 −1 над полем GF (2). Относительно умножения на 2 вычетыпо модулю 15 разбиваются на такие орбиты:{0}, {1, 2, 4, 8}, {3, 6, 12, 9}, {5, 10}, {7, 14, 13, 11}.164Глава 3.Конечные поля или поля ГалуаПоэтому x15 − 1 разлагается в произведение одного неприводимого многочлена степени 1, одного неприводимого многочлена степени 2 и трех неприводимых многочленов степени 4(см.
разложение на с. 148).Пример 3.56. Рассмотрим разложение многочлена x23 − 1над полем GF (2). Относительно умножения на 2 вычеты помодулю 23 разбиваются на три орбиты:{0}, {1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12},{5, 10, 20, 17, 11, 22, 21, 19, 15, 7, 14}.Поэтому x23 −1 разлагается в произведение одного неприводимого многочлена степени 1 и двух неприводимых многочленовстепени 11.3.10. Задачи3.1.
Доказать, что минимальное подполе любого поля характеристики 0 изоморфно полю рациональных чисел.3.2. Доказать, что минимальное подполе любого поля характеристики p изоморфно полю GF (p).3.3. Решить уравнение 4x = 1 в поле Z/(101).3.4. Найти 73−1 в поле Z/(103).3.5. Решить систему уравнений x + 2z = 1,y + 2z = 2,2x + z = 1в поле вычетов по модулю 3 и по модулю 5.3.6. Решить систему уравнений 3x + y + 2z = 1,x + 2y + 3z = 1,4x + 3y + 2z = 1в поле вычетов по модулю 5 и по модулю 7.3.7. Ненулевой вычет a называется квадратичным вычетом по модулю p, если уравнение x2 = a имеет решение в полеZ/(p).
В противном случае вычет называется квадратичным3.10.165Задачиневычетом. Чего больше: квадратичных вычетов или квадратичных невычетов?3.8. Доказать, что a является квадратичным вычетом понечетному простому модулю p тогда и только тогда, когдаa(p−1)/2 = 1 (mod p).3.9. Найти произведение всех квадратичных вычетов помодулю 71.3.10. Найти сумму всех квадратичных вычетов по модулю67.3.11. (Теорема Вильсона.) Доказать, что(p − 1)! ≡ −1 (mod p)для простого p.3.12.
Доказать, что в поле GF (p) выполняются равенства:p−1X1= 0 (p > 2);а)k(p−1)/2б)k=1k=120062006X20061= 0 (p > 3).k23.13. Найти 1+2+3+ · · · + 162006 по модулю 17.3.14. Сколько решений имеет уравнение x2 = a в полеGF (2n )?3.15. Для каких из чисел n = 2, 3, 4, 5, 6, 7 существует полеиз n элементов?3.16. В поле F выполнено равенство 5 = 21. Верно ли, чтов поле F выполнено равенство 7 = 15?3.17.
Можно ли в поле из 64 элементов найти подполе из 16элементов?3.18. Доказать, что поле из p2 элементов, где p — простоечисло, имеет единственное собственное подполе.3.19*. а) Доказать, что если многочлены f (x) и g(x) с целыми коэффициентами взаимно просты над полем вычетов попростому модулю p, причем хотя бы один из старших коэффициентов не делится на p, то эти многочлены взаимно простынад полем рациональных чисел.б) Показать на примере, что для любого простого числа pобратное утверждение не верно.3.20. Доказать, что многочлены f (x) и g(x) с целыми коэффициентами тогда и только тогда взаимно просты над полемрациональных чисел, когда они взаимно просты над полем166Глава 3.Конечные поля или поля Галуавычетов по модулю p, где p — любое простое число, исключая,быть может, конечное множество таких чисел.3.21*.
Доказать, что если многочлен f (x) с целыми коэффициентами приводим над полем рациональных чисел, то онприводим над полем вычетов по любому простому модулю p,не делящему старший коэффициент. Привести пример многочлена, приводимого над полем рациональных чисел, но неприводимого над полем вычетов по модулю p, где p делит старшийкоэффициент.3.22*. Существуют многочлены с целыми коэффициентами,неприводимые над полем рациональных чисел, но приводимыенад полем вычетов по любому простому модулю p.
Доказать,что таким будет, например, многочлен f (x) = x4 −10x2 +1. Этомногочлен наименьшейс целыми коэффициентами,√ степени√имеющий корень α = 2 + 3.3.23. Многочлен f (x) = x2 +ax+b, a, b ∈ GF (5), неприводимнад GF (5). Верно ли, что f (x) неприводим над GF (125)?3.24.
Доказать, что n! делит(pn − 1)(pn − p)(pn − p2 ) . . . (pn − pn−1 ).3.25. Решить уравнение xp − x = 0 в поле GF (pn ).3.26. Решить уравнение 5x − 7 = 0 в поле из 169 элементов.3.27. Решить уравнение x2 + x + 4 = 0 в поле GF (121).3.28. Сколько решений имеет уравнение x23 − x7 − 1 = 0 вполе GF (24 )?3.29. Производная многочлена f 6= 0 над полем характеристики p тождественно равна 0.
Доказать, что этот многочленприводимый.3.30. Доказать, что многочлен f над полем F характеристики p, который взаимно прост со своей производной f ′ , неприводим тогда и только тогда, когда уравнение xp = x имеет вкольце F [x]/(f ) ровно p решений.3.31.
Пусть (f, f ′ ) = 1 и v p = v в кольце F [x]/(f ), v ∈/{0, 1, . . . , p − 1}. (Здесь p — характеристика поля коэффициентов F .) Доказать, что тогда для некоторого a ∈ F многочленыv − a и f имеют нетривиальный общий делитель.3.32. Доказать, что любая функция f : GF (pn ) → GF (pn )может быть представлена многочленом.3.10.Задачи1673.33. Является ли x4 + 1 неприводимым многочленом надполем GF (3)?3.34. Многочлен x5 +x3 +x2 +1 разложить на неприводимыемножители над полем вычетов по модулю 2.3.35.
Многочлен x3 + 2x2 + 4x + 1 разложить на неприводимые множители над полем вычетов по модулю 5.3.36. Многочлен x4 + x3 + x+ 2 разложить на неприводимыемножители над полем вычетов по модулю 3.3.37. Многочлен x4 + 3x3 + 2x2 + x + 4 разложить на неприводимые множители над полем вычетов по модулю 5.3.38. Разложить на неприводимые множители над полемвычетов по модулю 2 все нормированные многочлены второйстепени от x.3.39. Разложить на неприводимые множители над полемвычетов до модулю 2 все нормированные многочлены третьейстепени от x.3.40.
Найти все нормированные многочлены второй степени от x, неприводимые над полем вычетов по модулю 3.3.41. Найти все нормированные многочлены третьей степени от x, неприводимые над полем вычетов по модулю 3.3.42. а) Проверить, что F = GF (7)[x]/(x2 + x − 1) являетсяполем. б) Выразите обратный к 1 − x в F в базисе 1, x.3.43. Найти порядок элемента x + x2 в мультипликативнойгруппеа) поля GF (2)[x]/(x4 + x + 1);б) поля GF (2)[x]/(x4 + x3 + 1).3.44. Найти количество неприводимых многочленова) степени 7 над полем GF (2);б) степени 6 над полем GF (5);в) степени 24 над полем GF (3).3.45. Чему равно произведение всех ненулевых элементовполя GF (26 )?3.46.
Чему равна сумма всех элементов поля GF (37 )?3.47. Многочлен f ∈ GF (13)[x] седьмой степени разлагается над GF (13) на неприводимые множители степени 3 и 4.В каких полях GF (13n ) многочлен f разлагается на линейныемножители?3.48. Найти наименьшее поле характеристики 2, в котороммногочлен x19 − 1 разлагается на линейные множители.168Глава 3.Конечные поля или поля Галуа3.49.
Построить изоморфизм между полямиGF (7)[x]/(x2 + x − 1) и GF (7)[x]/(x2 + 1).3.50. Доказать, что группа автоморфизмов поля GF (pn ) —циклическая, а ее порождающим является автоморфизм Фробениуса.3.51. Конечная проективная плоскость порядка n — это такое семейство подмножеств L1 , . . . , Lm («прямых») конечногомножества «точек» P , что выполняются следующие свойства:• через каждую точку проходит n + 1 прямая;• каждая прямая содержит n + 1 точку;• через любые две различные точки проходит ровно однапрямая;• любые две различные прямые пересекаются ровно по одной точке.Построить конечную проективную плоскость порядка q,где q — степень простого числа.3.52.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
