PA_full (1127144), страница 9
Текст из файла (страница 9)
, an 2 ).Прикладная алгебраПоля ГалуаЦиклические подпространства102 / 432Кольцо классов вычетов по модулю многочлена xn1В кольце p /(xn 1), рассматриваемом как векторноепространство над полем p в базисе { 1, x, . . . , xn 1 }.Циклический сдвиг координат в этом базисе равносиленумножению на x:(a0 + a1 x + . . . + an1xn 1)·x == (a0 x + a1 x2 + . . . + an= (an11xn)=+ a0 x + a1 x2 + . . . + an2xn 1 ).Прикладная алгебраПоля ГалуаЦиклические подпространстваИдеал вp /(xn103 / 4321) � циклическое пространствоТеоремаПусть I ✓ p /(xn 1).Тогда I � циклическое пространство , I Cp /(xn1).Прикладная алгебраПоля ГалуаЦиклические подпространстваИдеал вp /(xn103 / 4321) � циклическое пространствоТеоремаПусть I ✓ p /(xn 1).Тогда I � циклическое пространство , I Cp /(xn1).ДоказательствоЕсли подпространство I � идеал, то оно замкнутоотносительно умножения на x, а это умножение и естьциклический сдвиг.Прикладная алгебраПоля ГалуаЦиклические подпространстваИдеал вp /(xn103 / 4321) � циклическое пространствоТеоремаПусть I ✓ p /(xn 1).Тогда I � циклическое пространство , I Cp /(xn1).ДоказательствоЕсли подпространство I � идеал, то оно замкнутоотносительно умножения на x, а это умножение и естьциклический сдвиг.Пусть I � циклическое подпространство I и g 2 I.Тогда g · x, g · x2 , .
. . � циклические сдвиги, т.е. такжепринадлежат I.Значит, g · f 2 I для любого многочлена f ,поэтому I � идеал.Прикладная алгебраПоля ГалуаЦиклические подпространстваПримитивные корниПоказано: любой многочлен с коэффициентами из pразлагается на линейные множители в некотором поле qхарактеристики p.Пусть q � поле характеристики p, в котором разлагаетсямногочлен xn 1.104 / 432Прикладная алгебраПоля ГалуаЦиклические подпространстваПримитивные корниПоказано: любой многочлен с коэффициентами из pразлагается на линейные множители в некотором поле qхарактеристики p.Пусть q � поле характеристики p, в котором разлагаетсямногочлен xn 1.
Справедливо:В q выполняется равенство xkp 1 = (xk 1)p , поэтомуинтересен случай, когда n взаимно просто с p: тогда умногочлена xn 1 кратных корней нет (он взаимно простсо своей производной nxn 1 ).Равенство xn = 1 означает, что порядок элемента xв мультипликативной циклической группе ⇤q делит n.Вывод: корни уравнения xn 1 = 0 образуют группу корнейстепени n из единицы � подгруппу в ⇤q .Эта подгруппа также циклическая; её порождающие элементыназываются примитивными корнями степени n.104 / 432Прикладная алгебраПоля ГалуаЦиклические подпространстваКоличество и степени неприводимых делителей xnПодгруппа в циклической группе существует iff её порядокделит порядок циклической группы )105 / 4321Прикладная алгебраПоля ГалуаЦиклические подпространства105 / 432Количество и степени неприводимых делителей xn1Подгруппа в циклической группе существует iff её порядокделит порядок циклической группы ) поле q содержит группукорней из единицы степени n iff n | q 1.Разложение xn121 надp:в поле q на линейные множители (корни степени n изединицы);в поле p на неприводимые множители.Какие корни из единицы будут неприводимыми делителямиxn 1 в p ?2Если � корень f (x), то p , p и т.д.
� также его корни )количество и степени неприводимых делителей xn 1 можнонайти, разбив p на орбиты отображения t 7! pt mod n.Прикладная алгебраПоля ГалуаЦиклические подпространстваРазложение многочлена x15106 / 4321 над полем2ПримерРассмотрим ещё раз разложение многочлена x15 1 надОтносительно умножения на 2 вычеты по модулю 15разбиваются на такие орбиты:2.{ 0 }, { 1, 2, 4, 8 }, { 3, 6, 12, 9 }, { 5, 10 }, { 7, 14, 13, 11 }Поэтому x151 разлагается в произведениеодного неприводимого многочлена степени 1,одного неприводимого многочлена степени 2,трех неприводимых многочленов степени 4.Конкретно (разложение было раньше): x15 + 1 == (x + 1)(x2 + x + 1)(x4 + x + 1)(x4 + x3 + 1)(x4 + x3 + x2 + x + 1).Прикладная алгебраПоля ГалуаЦиклические подпространстваРазложение многочлена x23107 / 4321 над полем2ПримерРассмотрим разложение многочлена x23 1 над 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 }(18 · 2 = 36 ⌘23 13)Поэтому x23 1 разлагается в произведение одногонеприводимого многочлена степени 1 и двух неприводимыхмногочленов степени 11.Прикладная алгебраПоля ГалуаЗадачиРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды108 / 432Прикладная алгебраПоля ГалуаЗадачиРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств109 / 432Прикладная алгебраПоля ГалуаЗадачиРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать110 / 432Прикладная алгебраПоля ГалуаЗадачи111 / 432Задача (ПГ-1 (Теорема Вильсона))Доказать, что (p1)! ⌘p1 для простого p.Прикладная алгебраПоля ГалуаЗадачи111 / 432Задача (ПГ-1 (Теорема Вильсона))Доказать, что (pРешениеp = 2:1)! ⌘p1 для простого p.� утверждение тривиально.Прикладная алгебраПоля ГалуаЗадачи111 / 432Задача (ПГ-1 (Теорема Вильсона))Доказать, что (p1)! ⌘p1 для простого p.Решениеp = 2: � утверждение тривиально.p > 2: Элементы p являются корнями уравненияxp 1 1 = 0 и других корней у этого уравнениянет (многочлен степени p 1 имеет не большеp 1 корня).По теореме Виета их произведение равносвободному члену -1.Прикладная алгебраПоля ГалуаЗадачиЗадачаНайти x ⌘17 12006 + 22006 + .
. . + 162006 .112 / 432Прикладная алгебраПоля ГалуаЗадачи112 / 432ЗадачаНайти x ⌘17 12006 + 22006 + . . . + 162006 .Решение⇤ = { 1, 2, . . . , 16 } = h3i:1731 = 1, 32 = 9, 33 = 27 ⌘17 10, 30 ⌘17 13, 39 ⌘17 5...;G = { 12006 , 22006 , . . . , 162006 } � циклическая подгруппапорядка k группы ⇤17 .Элементы G � корни уравненияxk1=0Их сумма по теореме Виета есть коэффициент при xk(⇤), т.е. 0.(⇤)1вПрикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-2)Производная многочлена f 6= 0 над полем характеристики pтождественно равна 0.Доказать, что этот многочлен приводимый.113 / 432Прикладная алгебраПоля ГалуаЗадачи113 / 432Задача (ПГ-2)Производная многочлена f 6= 0 над полем характеристики pтождественно равна 0.Доказать, что этот многочлен приводимый.Решениепроизводная монома (xn )0 = nxniff n ⌘p 0 , p | n;1тождественно равна 0f 0 = 0 ) показатели степеней всех мономов многочленаf делятся на p;поэтому f (x) = g(xp ) = g p (x).Прикладная алгебраПоля ГалуаЗадачи114 / 432Задача (ПГ-3)Доказать, что любая функция f :представлена многочленом.np!npможет бытьПрикладная алгебраПоля ГалуаЗадачи114 / 432Задача (ПГ-3)Доказать, что любая функция f :представлена многочленом.np!npможет бытьРешениеМожно, например, использовать интерполяционный многочленЛагранжа:Qb)Xb2 n r{a} (xf (x) =f (a) Q p.(a b)b2 nnp r{a}↵2pПрикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-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 разложить на неприводимыемножители над полем 5 .116 / 432Прикладная алгебраПоля ГалуаЗадачи116 / 432Задача (ПГ-5)Многочлен f = x3 + 2x2 + 4x + 1 разложить на неприводимыемножители над полем 5 .Решение12f (2) = 23 + 2 · 22 + 4 · 22 + 1 = 25 ⌘5 0, (xx3 + 2x2 + 4x + 1x+3x3 + 3x2x2 + 4x + 24x2 + 4x4x2 + 2x2x + 12x + 103многочлен f1 = x2 + 4x + 2 неприводим в5Ответ: x3 + 2x2 + 4x + 1 = (x + 3)(x2 + 4x + 2).2) ⌘5 (x + 3)Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-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Неприводимые многочлены над3степени 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
