Лекции по прикладной алгебре. v1.1 (1127111), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

Тогда1совокупность всех вычетов, кратных ϕ, образует идеал вкольце классов вычетов по модулю f :Iϕ = { t · ϕ } C Fp [x]/(f ).ϕ — единственный нормированный многочленминимальной степени в Iϕ .def2Доказательство(f ) = tf,t, s, ϕ ∈ Fp [x],ϕ = a0 + a1 x + . . . + ak−1 xdeg f > deg ϕ = kk−1+ 1 · xk ,f = ψϕ.Прикладная алгебраПоля ГалуаЦиклические подпространства89 / 160Нормированный делитель...Проверим, что Iϕ — идеал.1g ∈ Iϕh⊆g⇔g = uϕh = vg = vuϕ2g, h ∈ Iϕ ⇔g = uϕh = vϕg + h = (u + v)ϕ ∈ Iϕ .⇒ h ∈ Iϕ .Прикладная алгебраПоля ГалуаЦиклические подпространстваНормированный делитель...Покажем, что в Iϕ нет других, кромеϕ = a0 + a1 x + .

. . + ak−1 xk−1 + xkнормированных многочленов степени, меньшей k = deg ϕ.Пустьω = b0 + b1 x + . . . + xm .Тогда:ω ∈ Iϕ ⇔ ω = tϕ ⇒ deg ω = m > deg ϕ.90 / 160Прикладная алгебраПоля ГалуаЦиклические подпространстваПодыдеал как векторное пространствоТеоремаПусть ϕ — неприводимый нормированный делительмногочлена f ∈ Fp [x] отличный от f , deg f = n, deg ϕ = k.Тогда идеал (ϕ) — векторное пространство размерности n − k.91 / 160Прикладная алгебраПоля ГалуаЦиклические подпространстваПодыдеал как векторное пространствоТеоремаПусть ϕ — неприводимый нормированный делительмногочлена f ∈ Fp [x] отличный от f , deg f = n, deg ϕ = k.Тогда идеал (ϕ) — векторное пространство размерности n − k.ДоказательствоБез доказательства.91 / 160Прикладная алгебраПоля ГалуаЦиклические подпространстваЦиклическое пространство: определениеПусть F — n-мерное векторное пространство наднеоторым полем.Фиксируем некоторый базис F .ТогдаF ∼= F n = { (a0 , .

. . , an−1 ) | ai ∈ F, i = 0, 1, . . . , n − 1 } —координатное пространство.ОпределениеПодпространство координатного пространства F n называетсяциклическим, если вместе с набором (a0 , . . . , an−1 ) оносодержит циклический сдвиг этого набора, т.е. набор(an−1 , a0 , . . . , an−2 ).92 / 160Прикладная алгебраПоля ГалуаЦиклические подпространства93 / 160Кольцо классов вычетов по модулю многочлена xn − 1В кольце Fp /(xn − 1), рассматриваемом как векторноепространство над полем Fp в базисе { 1, x, . . . , xn−1 }.Циклический сдвиг координат в этом базисе равносиленумножению на x:(a0 + a1 x + .

. . + an−1 xn−1 ) · x == (a0 x + a1 x2 + . . . + an−1 xn ) == (an−1 + a0 x + a1 x2 + . . . + an−2 xn−1 ).Прикладная алгебраПоля ГалуаЦиклические подпространстваИдеал вFp /(xn − 1) — циклическое пространствоТеоремаПусть I ⊆ Fp /(xn − 1).Тогда I — циклическое пространство ⇔ I C Fp /(xn − 1).94 / 160Прикладная алгебраПоля ГалуаЦиклические подпространстваИдеал вFp /(xn − 1) — циклическое пространствоТеоремаПусть I ⊆ Fp /(xn − 1).Тогда I — циклическое пространство ⇔ I C Fp /(xn − 1).ДоказательствоЕсли подпространство I — идеал, то оно замкнутоотносительно умножения на x, а это умножение и естьциклический сдвиг.94 / 160Прикладная алгебраПоля ГалуаЦиклические подпространстваИдеал вFp /(xn − 1) — циклическое пространствоТеоремаПусть I ⊆ Fp /(xn − 1).Тогда I — циклическое пространство ⇔ I C Fp /(xn − 1).ДоказательствоЕсли подпространство I — идеал, то оно замкнутоотносительно умножения на x, а это умножение и естьциклический сдвиг.Пусть I — циклическое подпространство I и g ∈ I.Тогда g · x, g · x2 , .

. . — циклические сдвиги, т.е. такжепринадлежат I.Значит, g · f ∈ I для любого многочлена f , поэтому I —идеал.94 / 160Прикладная алгебраПоля ГалуаЦиклические подпространстваПримитивные корниПоказано: любой многочлен с коэффициентами из Fpразлагается на линейные множители в некотором поле Fqхарактеристики p.Пусть Fq — поле характеристики p, в котором разлагаетсямногочлен xn − 1.95 / 160Прикладная алгебраПоля ГалуаЦиклические подпространстваПримитивные корниПоказано: любой многочлен с коэффициентами из Fpразлагается на линейные множители в некотором поле Fqхарактеристики p.Пусть Fq — поле характеристики p, в котором разлагаетсямногочлен xn − 1.

Справедливо:В Fq выполняется равенство xkp − 1 = (xk − 1)p , поэтомуинтересен случай, когда n взаимно просто с p: тогда умногочлена xn − 1 кратных корней нет (он взаимно простсо своей производной nxn−1 ).Равенство xn = 1 означает, что порядок элемента xв мультипликативной циклической группе F∗q делит n.Вывод: корни уравнения xn − 1 = 0 образуют группу корнейстепени n из единицы — подгруппу в F∗q .Эта подгруппа также циклическая; её порождающие элементыназываются примитивными корнями степени n.95 / 160Прикладная алгебраПоля ГалуаЦиклические подпространстваКоличество и степени неприводимых делителей xn − 1Подгруппа в циклической группе существует iff её порядокделит порядок циклической группы ⇒96 / 160Прикладная алгебраПоля ГалуаЦиклические подпространства96 / 160Количество и степени неприводимых делителей xn − 1Подгруппа в циклической группе существует iff её порядокделит порядок циклической группы ⇒ поле Fq содержит группукорней из единицы степени n iff n | q − 1.Разложение xn − 1 над12Fp :в поле Fq на линейные множители (корни степени n изединицы);в поле Fp на неприводимые множители.Какие корни из единицы будут неприводимыми делителямиxn − 1 в Fp ?2Если β — корень f (x), то β p , β p и т.д.

— также его корни ⇒количество и степени неприводимых делителей xn − 1 можнонайти, разбив Fp на орбиты отображения t 7→ pt mod n.Прикладная алгебраПоля ГалуаЦиклические подпространстваРазложение многочлена x15 − 1 над полем97 / 160F2ПримерРассмотрим ещё раз разложение многочлена 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).Прикладная алгебраПоля ГалуаЦиклические подпространства98 / 160Разложение многочлена x23 − 1 над полемF2ПримерРассмотрим разложение многочлена 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Коды, исправляющие ошибкиОсновная задача теории кодированияЦиклические коды99 / 160Прикладная алгебраПоля ГалуаЗадачиРаздел IIКоды БЧХЧто надо знать100 / 160Прикладная алгебраПоля ГалуаЗадачиЗадача (Теорема Вильсона)Доказать, что (p − 1)! ≡p −1 для простого p.101 / 160Прикладная алгебраПоля ГалуаЗадачи101 / 160Задача (Теорема Вильсона)Доказать, что (p − 1)! ≡p −1 для простого p.Решениеp = 2:— утверждение тривиально.Прикладная алгебраПоля ГалуаЗадачиЗадача (Теорема Вильсона)Доказать, что (p − 1)! ≡p −1 для простого p.Решениеp = 2: — утверждение тривиально.p > 2: Элементы Fp являются корнями уравненияxp−1 − 1 = 0 и других корней у этого уравнениянет (многочлен степени p − 1 имеет не большеp − 1 корня).По теореме Виета их произведение равносвободному члену -1.101 / 160Прикладная алгебраПоля ГалуаЗадачиЗадачаНайти x ≡17 12006 + 22006 + .

. . + 162006 .102 / 160Прикладная алгебраПоля ГалуаЗадачи102 / 160ЗадачаНайти 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 в(∗), т.е.

Характеристики

Список файлов лекций