Лекции по прикладной алгебре. v2.0 (1127112), страница 9
Текст из файла (страница 9)
— также его корни ⇒количество и степени неприводимых делителей xn − 1 можнонайти, разбив Fp на орбиты отображения t 7→ pt mod n.Прикладная алгебраПоля ГалуаЦиклические подпространстваРазложение многочлена x15 − 1 над полем106 / 432F2ПримерРассмотрим ещё раз разложение многочлена x15 − 1 надОтносительно умножения на 2 вычеты по модулю 15разбиваются на такие орбиты:F2 .{ 0 }, { 1, 2, 4, 8 }, { 3, 6, 12, 9 }, { 5, 10 }, { 7, 14, 13, 11 }Поэтому x15 − 1 разлагается в произведениеодного неприводимого многочлена степени 1,одного неприводимого многочлена степени 2,трех неприводимых многочленов степени 4.Конкретно (разложение было раньше): x15 + 1 == (x + 1)(x2 + x + 1)(x4 + x + 1)(x4 + x3 + 1)(x4 + x3 + x2 + x + 1).Прикладная алгебраПоля ГалуаЦиклические подпространстваРазложение многочлена x23 − 1 над полем107 / 432F2ПримерРассмотрим разложение многочлена x23 − 1 над F2 .Относительно умножения на 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 }(18 · 2 = 36 ≡23 13)Поэтому x23 − 1 разлагается в произведение одногонеприводимого многочлена степени 1 и двух неприводимыхмногочленов степени 11.Прикладная алгебраПоля ГалуаЗадачиРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды108 / 432Прикладная алгебраПоля ГалуаЗадачиРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств109 / 432Прикладная алгебраПоля ГалуаЗадачиРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у.
множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать110 / 432Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-1 (Теорема Вильсона))Доказать, что (p − 1)! ≡p −1 для простого p.111 / 432Прикладная алгебраПоля ГалуаЗадачи111 / 432Задача (ПГ-1 (Теорема Вильсона))Доказать, что (p − 1)! ≡p −1 для простого p.Решениеp = 2:— утверждение тривиально.Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-1 (Теорема Вильсона))Доказать, что (p − 1)! ≡p −1 для простого p.Решениеp = 2: — утверждение тривиально.p > 2: Элементы Fp являются корнями уравненияxp−1 − 1 = 0 и других корней у этого уравнениянет (многочлен степени p − 1 имеет не большеp − 1 корня).По теореме Виета их произведение равносвободному члену -1.111 / 432Прикладная алгебраПоля ГалуаЗадачиЗадачаНайти x ≡17 12006 + 22006 + .
. . + 162006 .112 / 432Прикладная алгебраПоля ГалуаЗадачи112 / 432ЗадачаНайти x ≡17 12006 + 22006 + . . . + 162006 .РешениеF∗17 = { 1, 2, . . . , 16 } = h3i:31 = 1, 32 = 9, 33 = 27 ≡17 10, 30 ≡17 13, 39 ≡17 5...;G = { 12006 , 22006 , . . . , 162006 } — циклическая подгруппапорядка k группы F∗17 .Элементы G — корни уравненияxk − 1 = 0(∗)Их сумма по теореме Виета есть коэффициент при xk−1 в(∗), т.е. 0.Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-2)Производная многочлена f 6= 0 над полем характеристики pтождественно равна 0.Доказать, что этот многочлен приводимый.113 / 432Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-2)Производная многочлена f 6= 0 над полем характеристики pтождественно равна 0.Доказать, что этот многочлен приводимый.Решениепроизводная монома (xn )0 = nxn−1 тождественно равна 0iff n ≡p 0 ⇔ p | n;f 0 = 0 ⇒ показатели степеней всех мономов многочленаf делятся на p;поэтому f (x) = g(xp ) = g p (x).113 / 432Прикладная алгебраПоля ГалуаЗадачи114 / 432Задача (ПГ-3)Доказать, что любая функция f :представлена многочленом.Fnp → Fnp может бытьПрикладная алгебраПоля ГалуаЗадачи114 / 432Задача (ПГ-3)Доказать, что любая функция f :представлена многочленом.Fnp → Fnp может бытьРешениеМожно, например, использовать интерполяционный многочленЛагранжа:QXb∈Fn r{a} (x − b)f (x) =f (a) Q p.(a − b)b∈Fnnp r{a}α∈FpПрикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-4)Многочлен x5 + x3 + x2 + 1 разложить на неприводимыемножители над полем вычетов по модулю 2.115 / 432Прикладная алгебраПоля ГалуаЗадачи115 / 432Задача (ПГ-4)Многочлен x5 + x3 + x2 + 1 разложить на неприводимыемножители над полем вычетов по модулю 2.Решение1f (x) = x5 + x3 + x2 + 1, f (1) = 0 ⇒ 1 — корень f .2Делим f на x = 1, получаем x4 + x3 + x + 1 = f1 (x).3f1 (1) = 0 ⇒ 1 — корень f1 ;f1x+1= x3 + 1 = f2 (x).4f2 (1) = 0 ⇒ 1 — корень f2 ;f2x+1= x2 + x + 1.5Многочлен x2 + x + 1 неприводим.Ответ: x5 + x3 + x2 + 1 = (x + 1)3 (x2 + x + 1).Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-5)Многочлен f = x3 + 2x2 + 4x + 1 разложить на неприводимыемножители над полем F5 .116 / 432Прикладная алгебраПоля ГалуаЗадачи116 / 432Задача (ПГ-5)Многочлен f = x3 + 2x2 + 4x + 1 разложить на неприводимыемножители над полем F5 .Решение1f (2) = 23 + 2 · 22 + 4 · 22 + 1 = 25 ≡5 0, (x − 2) ≡5 (x + 3)2x3 + 2x2 + 4x + 1x+3x3 + 3x2x2 + 4x + 24x2 + 4x4x2 + 2x2x + 12x + 103многочлен f1 = x2 + 4x + 2 неприводим вF5Ответ: x3 + 2x2 + 4x + 1 = (x + 3)(x2 + 4x + 2).Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-6)Многочлен f (x) = x4 + x3 + x + 2 разложить на неприводимыемножители над полем вычетов по модулю 3.117 / 432Прикладная алгебраПоля ГалуаЗадачи117 / 432Задача (ПГ-6)Многочлен f (x) = x4 + x3 + x + 2 разложить на неприводимыемножители над полем вычетов по модулю 3.Решение1 0, 1, 2 — не корни f (x) ⇒ f (x) линейных делителей несодержит.2Неприводимые многочлены надF3 степени 2:x2 + 1,x2 + x + 2,x2 + 2x + 2.3Подбором получаем: f (x) = (x2 + 1)(x2 + x + 2).Ответ: (x2 + 1)(x2 + x + 2).Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-7)Многочлен x4 + 3x3 + 2x2 + x + 4 разложить на неприводимыемножители над полем вычетов по модулю 5.118 / 432Прикладная алгебраПоля ГалуаЗадачи118 / 432Задача (ПГ-7)Многочлен x4 + 3x3 + 2x2 + x + 4 разложить на неприводимыемножители над полем вычетов по модулю 5.Решение1.
Убеждаемся, что многочлен f (x) = x4 + 3x3 + 2x2 + x + 4не имеет линейных делителей:f (x) 6= 0 ни при одном x = 0, 1, 2, 3, 4.2. Перебирая неприводимые многочлены степени 2 надполучаемf (x) = (x2 + x + 1)(x2 + 2x + 4).F5 ,Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-8)Разложить на неприводимые множители над полем вычетов помодулю 2 все нормированные многочлены второй степени от x.119 / 432Прикладная алгебраПоля ГалуаЗадачи119 / 432Задача (ПГ-8)Разложить на неприводимые множители над полем вычетов помодулю 2 все нормированные многочлены второй степени от x.Решениеf1 (x) = x2 = x · x,f2 (x) = x2 + 1 = (x + 1)2 ,f3 (x) = x2 + x = x · (x + 1),f4 (x) = x2 + x + 1 — неприводим.Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-9)Разложить на неприводимые множители над полем вычетов домодулю 2 все нормированные многочлены третьей степени от x.120 / 432Прикладная алгебраПоля ГалуаЗадачи120 / 432Задача (ПГ-9)Разложить на неприводимые множители над полем вычетов домодулю 2 все нормированные многочлены третьей степени от x.Решениеf1 (x) = x3 ,f2 (x) = x3 + 1 = (x + 1)(x2 + x + 1),f3 (x) = x3 + x = x(x + 1)2 ,f4 (x) = x3 + x2 = x2 (x + 1),f5 (x) = x3 + x + 1 — неприводим,f6 (x) = x3 + x2 + 1 — неприводим,f7 (x) = x3 + x2 + x = x(x2 + x + 1),f8 (x) = x3 + x2 + x + 1 = (x + 1)3 .Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-10)Найти все нормированные многочлены второй степени от x,неприводимые над полем вычетов по модулю 3.121 / 432Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-10)Найти все нормированные многочлены второй степени от x,неприводимые над полем вычетов по модулю 3.РешениеДолжно быть: f (0) 6= 0, f (1) 6= 0, f (2) 6= 0.121 / 432Прикладная алгебраПоля ГалуаЗадачи121 / 432Задача (ПГ-10)Найти все нормированные многочлены второй степени от x,неприводимые над полем вычетов по модулю 3.РешениеДолжно быть: f (0) 6= 0, f (1) 6= 0, f (2) 6= 0.
Переборомкоэффициентов в выражении x2 + bx + c, находим подходящиемногочлены:f1 (x) = x2 + 1,f2 (x) = x2 + x + 2,f3 (x) = x2 + 2x + 2.Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-11)Найти все нормированные многочлены третьей степени от x,неприводимые над полем вычетов по модулю 3.122 / 432Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-11)Найти все нормированные многочлены третьей степени от x,неприводимые над полем вычетов по модулю 3.РешениеДолжно быть: f (0) 6= 0, f (1) 6= 0, f (2) 6= 0.122 / 432Прикладная алгебраПоля ГалуаЗадачи122 / 432Задача (ПГ-11)Найти все нормированные многочлены третьей степени от x,неприводимые над полем вычетов по модулю 3.РешениеДолжно быть: f (0) 6= 0, f (1) 6= 0, f (2) 6= 0.f1 (x) = x3 + 2x + 1,f2 (x) = x3 + 2x + 2,f3 (x) = x3 + x2 + 2,f4 (x) = x3 + 2x2 + 1,f5 (x) = x3 + x2 + x + 2,f6 (x) = x3 + x2 + 2x + 1,f7 (x) = x3 + 2x2 + x + 1,f8 (x) = x3 + 2x2 + 2x + 2.Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-12)12Проверить, что F = F7 [x]/(x2 + x − 1) является полем.Выразить обратный к 1 − x в F в базисе { 1, x }.123 / 432Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-12)12Проверить, что F = F7 [x]/(x2 + x − 1) является полем.Выразить обратный к 1 − x в F в базисе { 1, x }.Решение1f (x) = x2 + x − 1, f (0) = 6, f (1) = 1, f (2) = 5, f (3) = 4,f (4) = 6, f (5) = 1, f (6) = 6 ⇒многочлен f (x) — неприводим в F7 и F — поле (= F27 ).123 / 432Прикладная алгебраПоля ГалуаЗадачи123 / 432Задача (ПГ-12)12Проверить, что F = F7 [x]/(x2 + x − 1) является полем.Выразить обратный к 1 − x в F в базисе { 1, x }.Решение1f (x) = x2 + x − 1, f (0) = 6, f (1) = 1, f (2) = 5, f (3) = 4,f (4) = 6, f (5) = 1, f (6) = 6 ⇒многочлен f (x) — неприводим в F7 и F — поле (= F27 ).2F27= { ax + b | a, b ∈ F7 , x2 = 1 − x = 6x + 1 }(ax + b) · (6x + 1) = .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
