PA_full (1127144), страница 11
Текст из файла (страница 11)
Теперь, перебирая все возможные значения a, b 2все элементы идеала x2 + x + 2 :a000111222b012012012ax3 + (a + b)x2 + (2a + b)x + 2b0x2 + x + 22x2 + 2x + 1x3 + x2 + 2xx3 + 2x2 + 2x3 + x + 12x3 + 2x2 + x2x3 + 2x + 22x3 + x2 + 13,найдёмПрикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-20)В поле 7 [x]/(x4 + x3 + x2 + 3) найти обратный элемент дляx2 + x + 3.135 / 432Прикладная алгебраПоля ГалуаЗадачи135 / 432Задача (ПГ-20)В поле 7 [x]/(x4 + x3 + x2 + 3) найти обратный элемент дляx2 + x + 3.РешениеПроще всего обратный элемент можно найти путём решенияуравнения(x4 + x3 + x2 + 3) · a(x) +(x2 + x + 3) · b(x) = 1|{z}(⇤)=0с помощью расширенного алгоритма Евклида � тогда b(x)будет искомым обратным элементом.Замечание: вычислять коэффициент при x4 + x3 + x2 + 3(xi (x)) нет необходимости (нас интересует только коэффициентпри x2 + x + 3, т.е. yi (x)).Прикладная алгебраПоля ГалуаЗадачи136 / 432Решение (продолжение -1)Шаг 0.Шаг 1.Шаг 2.r 2 (x) = x4 + x3 + x2 + 3, // Инициализацияr 1 (x) = x2 + x + 3,y 2 (x) = 0,y 1 (x) = 1.r 2 (x) = r 1 (x)q0 (x) + r0 (x),// Делим r 2 (x) на r 1 (x) с остаткомq0 (x) = x2 + 5,r0 (x) = 2x + 2,y0 (x) = y 2 (x) y 1 (x)q0 (x) = q0 (x) = x2 5.r 1 (x) = r0 (x)q1 (x) + r1 (x),// Делим r 1 (x) на r0 (x) с остаткомq1 (x) = 4x,r1 (x) = 3,y1 (x) = y 1 (x) y0 (x)q1 (x) = 1 + 4x(x2 + 5) == 4x3 + 6x + 1.Прикладная алгебраПоля ГалуаЗадачи137 / 432Решение (продолжение -2)Алгоритм заканчивает свою работу на Шаге 2, т.к.
степень 0очередного остатка r1 (x) = 3 равна степени многочлена в правойчасти (⇤): 1 � многочлен 0-й степени.Прикладная алгебраПоля ГалуаЗадачи137 / 432Решение (продолжение -2)Алгоритм заканчивает свою работу на Шаге 2, т.к. степень 0очередного остатка r1 (x) = 3 равна степени многочлена в правойчасти (⇤): 1 � многочлен 0-й степени.В результате работы алгоритма получено:(x2 + x + 3)(4x3 + 6x + 1) = r1 (x) = 3.Прикладная алгебраПоля ГалуаЗадачи137 / 432Решение (продолжение -2)Алгоритм заканчивает свою работу на Шаге 2, т.к. степень 0очередного остатка r1 (x) = 3 равна степени многочлена в правойчасти (⇤): 1 � многочлен 0-й степени.В результате работы алгоритма получено:(x2 + x + 3)(4x3 + 6x + 1) = r1 (x) = 3.Чтобы найти b(x), нужно домножить y1 (x) на 31= 5:b(x) = 5y1 (x) = 5 · (4x3 + 6x + 1) = 6x3 + 2x + 5.Прикладная алгебраПоля ГалуаЗадачи137 / 432Решение (продолжение -2)Алгоритм заканчивает свою работу на Шаге 2, т.к. степень 0очередного остатка r1 (x) = 3 равна степени многочлена в правойчасти (⇤): 1 � многочлен 0-й степени.В результате работы алгоритма получено:(x2 + x + 3)(4x3 + 6x + 1) = r1 (x) = 3.Чтобы найти b(x), нужно домножить y1 (x) на 31= 5:b(x) = 5y1 (x) = 5 · (4x3 + 6x + 1) = 6x3 + 2x + 5.Проверка: b(x)(x2 + x + 3) = (6x3 + 2x + 5)(x2 + x + 3) == 6x5 + 6x4 + 6x3 + 4x + 1 == 6x( x3x23) + 6x4 + 6x3 + 4x + 1 = 1.Прикладная алгебраПоля ГалуаЗадачи138 / 432Задача (ПГ-21)В поле25=2+ 3x + 3) найти обратную для матрицы✓◆3x + 4 x + 2M =.x + 3 3x + 25 [x]/(xПрикладная алгебраПоля ГалуаЗадачи138 / 432Задача (ПГ-21)В поле25=2+ 3x + 3) найти обратную для матрицы✓◆3x + 4 x + 2M =.x + 3 3x + 25 [x]/(xРешениеДля матриц размера 2⇥2 обратная матрица записывается ввиде✓◆ 1✓◆1a bdb=.c dc aad bc1.
Сначала вычислим det M = adbc с учётом x2 = 2x + 2:det M = (3x+4)(3x+2) (x+2)(x+3) = 4x2 +3x+3 x2 1 == 3x2 + 3x + 2 = 3(2x + 2) + 3x + 2 = 4x + 3.Прикладная алгебраПоля ГалуаЗадачи139 / 432Решение (продолжение -1)2. Далее найдём обратный к 4x + 3 элемент решая уравнение(x2 + 3x + 3) · a(x) + (4x + 3) · b(x) = 1.с помощью расширенного алгоритма Евклида:Шаг 0.
r 2 (x) = x2 + 3x + 3, // Инициализацияr 1 (x) = 4x + 3,y 2 (x) = 0,y 1 (x) = 1.Шаг 1. r 2 (x) = r 1 (x)q0 (x) + r0 (x),// Делим r 2 (x) на r 1 (x) с остаткомq0 (x) = 4x + 4,r0 (x) = 1,y0 (x) = y 2 (x) y 1 (x)q0 (x) = q0 (x) == 4x 4 = x + 1.Т.е. (4x + 3) 1 = b(x) = y0 (x) = x + 1.Прикладная алгебраПоля ГалуаЗадачиРешение (продолжение -2;140 / 432x2 ⌘5 2x + 2)3. Наконец, вычислим обратную матрицу✓◆✓◆3x + 2 4x + 3x+3 11M= (x + 1)=.4x + 2 3x + 44x3xПрикладная алгебраПоля ГалуаЗадачиРешение (продолжение -2;140 / 432x2 ⌘5 2x + 2)3. Наконец, вычислим обратную матрицу✓◆✓◆3x + 2 4x + 3x+3 11M= (x + 1)=.4x + 2 3x + 44x3xПроверка (арифметические ошибки возможны!):✓◆ ✓◆3x + 4 x + 2x+3 1⇥=x + 3 3x + 24x3x✓◆(3x + 4)(x + 3) + 4x(x + 2) 3x + 4 + 3x(x + 2)==(x + 3)2 + 4x(3x + 2)x + 3 + 3x(3x + 2)✓◆2x2 + x + 2 3x2 + 4x + 4==3x2 + 4x + 4 4x2 + 2x + 3✓◆✓◆2(2x + 2) + x + 2 3(2x + 2) + 4x + 41 0==.3(2x + 2) + 4x + 4 4(2x + 2) + 2x + 30 1Прикладная алгебраПоля ГалуаЗадачи141 / 432Задача (ПГ-22)Разложить на неприводимые множители многочленf (x) = x11 + x9 + x8 + x4 + x3 + x2 + 1 22 [x].Прикладная алгебраПоля ГалуаЗадачи141 / 432Задача (ПГ-22)Разложить на неприводимые множители многочленf (x) = x11 + x9 + x8 + x4 + x3 + x2 + 1 2Решение1.
Сначала пытаемся найти корни f (x) вf(0) = 1,Значит, f (x) не имеет корней вмножителей.2 [x].2:f(1) = 1.2т.е. не имеет линейныхПрикладная алгебраПоля ГалуаЗадачи141 / 432Задача (ПГ-22)Разложить на неприводимые множители многочленf (x) = x11 + x9 + x8 + x4 + x3 + x2 + 1 2Решение1. Сначала пытаемся найти корни f (x) вf(0) = 1,Значит, f (x) не имеет корней вмножителей.2 [x].2:f(1) = 1.2т.е.
не имеет линейных2. Далее ищем делители f (x) среди неприводимыхмногочленов степени 2.Таковых над 2 только один � x2 + x + 1.При делении f (x) на x2 + x + 1, получаемf (x) = (x2 + x + 1) · (x9 + x8 + x7 + x6 + x4 + x3 + x2 + x + 1).Прикладная алгебраПоля ГалуаЗадачи142 / 432Решение (продолжение -1)Продолжаем дальше делить на x2 + x + 1:g(x) = x9 + x8 + x7 + x6 + x4 + x3 + x2 + x + 1 == (x2 + x + 1)(x7 + x4 + x3 + x2 + x + 1) + x,т.е.
x2 + x + 1 � делитель f (x) кратности 1.Прикладная алгебраПоля ГалуаЗадачи142 / 432Решение (продолжение -1)Продолжаем дальше делить на x2 + x + 1:g(x) = x9 + x8 + x7 + x6 + x4 + x3 + x2 + x + 1 == (x2 + x + 1)(x7 + x4 + x3 + x2 + x + 1) + x,т.е. x2 + x + 1 � делитель f (x) кратности 1.3. Неприводимых многочленов степени 3 над 2 два: x3 + x + 1и x3 + x2 + 1.
Пробуем поделить g(x) на x3 + x + 1:x9 + x8 + x7 + x6 + x4 + x3 + x2 + x + 1 == (x3 + x + 1)(x6 + x5 + x3 + x2 + 1).Прикладная алгебраПоля ГалуаЗадачиРешение (продолжение -2)Производя далее попытки деления h(x) = x6 + x5 + x3 + x2 + 1на многочлены 3-й степени, получаемx6 + x5 + x3 + x2 + 1 = (x3 + x + 1)(x3 + x2 + x + 1) + x2 ,x6 + x5 + x3 + x2 + 1 = (x3 + x2 + 1)x3 + x2 + 1.143 / 432Прикладная алгебраПоля ГалуаЗадачиРешение (продолжение -2)Производя далее попытки деления h(x) = x6 + x5 + x3 + x2 + 1на многочлены 3-й степени, получаемx6 + x5 + x3 + x2 + 1 = (x3 + x + 1)(x3 + x2 + x + 1) + x2 ,x6 + x5 + x3 + x2 + 1 = (x3 + x2 + 1)x3 + x2 + 1.Т.к.
как многочлен 6-ой степени h(x) не имеет делителей 3-й именьших степеней, то он является неприводимым: если бы онимел делитель, скажем, степени 4, то у него был бы и делительстепени 6 4 = 2.143 / 432Прикладная алгебраПоля ГалуаЗадачи143 / 432Решение (продолжение -2)Производя далее попытки деления h(x) = x6 + x5 + x3 + x2 + 1на многочлены 3-й степени, получаемx6 + x5 + x3 + x2 + 1 = (x3 + x + 1)(x3 + x2 + x + 1) + x2 ,x6 + x5 + x3 + x2 + 1 = (x3 + x2 + 1)x3 + x2 + 1.Т.к.
как многочлен 6-ой степени h(x) не имеет делителей 3-й именьших степеней, то он является неприводимым: если бы онимел делитель, скажем, степени 4, то у него был бы и делительстепени 6 4 = 2.В итоге в2 [x]имеем разложениеf (x) = x11 + x9 + x8 + x4 + x3 + x2 + 1 == (x2 + x + 1)(x3 + x + 1)(x6 + x5 + x3 + x2 + 1).Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-23)Найти минимальное поле характеристики 3, в котороммногочлен f (x) = x3 + x + 2 2 3 [x] раскладывается налинейные множители.В данном поле найти все корни данного многочлена.144 / 432Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-23)Найти минимальное поле характеристики 3, в котороммногочлен f (x) = x3 + x + 2 2 3 [x] раскладывается налинейные множители.В данном поле найти все корни данного многочлена.Решение1. Найдём разложение многочлена f (x) на неприводимыемножители над 3 .Проверяем корни: f (0) = 2, f (1) = 1, f (2) = 0.Т.к.
x 2 ⌘3 x + 1, то f (x) = (x + 1)(x2 + 2x + 2).Найдём разложение многочлена g(x) = x2 + 2x + 2 2 3 [x].Он не имеет корней, его степень = 2 ) он неприводим.Окончательно: f (x) = (x + 1)(x2 + 2x + 2).144 / 432Прикладная алгебраПоля ГалуаЗадачиРешение (продолжение -1)2.
Известно, что если g(x) � неприводимый многочлен степениn над конечным полем p , то он:145 / 432Прикладная алгебраПоля ГалуаЗадачи145 / 432Решение (продолжение -1)2. Известно, что если g(x) � неприводимый многочлен степениn над конечным полем p , то он:в поле своего расширения F = p [x]/(g(x))раскладывается на n линейных множителей �2g(x) = (x ↵) · (x ↵p ) · (x ↵p ) · . . . · (xгде ↵ – произвольный корень g(x) в F ;↵pn 1),не имеет корней ни в каком конечном поле, содержащимменее, чем pn элементов.Прикладная алгебраПоля ГалуаЗадачи145 / 432Решение (продолжение -1)2. Известно, что если g(x) � неприводимый многочлен степениn над конечным полем p , то он:в поле своего расширения F = p [x]/(g(x))раскладывается на n линейных множителей �2g(x) = (x ↵) · (x ↵p ) · (x ↵p ) · . . .
· (xгде ↵ – произвольный корень g(x) в F ;↵pn 1),не имеет корней ни в каком конечном поле, содержащимменее, чем pn элементов.3. Рассмотрим полеg(x) = x2 + 2x + 2.3 [x]/(g(x))расширения многочленаПрикладная алгебраПоля ГалуаЗадачи145 / 432Решение (продолжение -1)2. Известно, что если g(x) � неприводимый многочлен степениn над конечным полем p , то он:в поле своего расширения F = p [x]/(g(x))раскладывается на n линейных множителей �2g(x) = (x ↵) · (x ↵p ) · (x ↵p ) · . .
. · (xгде ↵ – произвольный корень g(x) в F ;↵pn 1),не имеет корней ни в каком конечном поле, содержащимменее, чем pn элементов.3. Рассмотрим поле 3 [x]/(g(x)) расширения многочленаg(x) = x2 + 2x + 2. В этом поле если ↵ � корень g(x), то↵2 =2↵2 = ↵ + 1;Прикладная алгебраПоля ГалуаЗадачи145 / 432Решение (продолжение -1)2. Известно, что если g(x) � неприводимый многочлен степениn над конечным полем p , то он:в поле своего расширения F = p [x]/(g(x))раскладывается на n линейных множителей �2g(x) = (x ↵) · (x ↵p ) · (x ↵p ) · . . . · (xгде ↵ – произвольный корень g(x) в F ;↵pn 1),не имеет корней ни в каком конечном поле, содержащимменее, чем pn элементов.3.
Рассмотрим поле 3 [x]/(g(x)) расширения многочленаg(x) = x2 + 2x + 2. В этом поле если ↵ � корень g(x), то↵2 = 2↵ 2 = ↵ + 1;↵3 = ↵(↵ + 1) = ↵2 + ↵ = 2↵ + 1 � тоже корень g(x)Прикладная алгебраПоля ГалуаЗадачи146 / 432Решение (продолжение -2;↵2 = ↵ + 1)Действительно (подчёркиваем слагаемые, дающие в сумме 0):(x↵)(x2↵21) = (x + 2↵) · (x + ↵ + 2) == x + ↵x + 2x + 2↵x + 2↵2 + 4↵ == x2 + 2x + 2↵ + 2 + 4↵ = x2 + 2x + 2.Прикладная алгебраПоля ГалуаЗадачи146 / 432Решение (продолжение -2;↵2 = ↵ + 1)Действительно (подчёркиваем слагаемые, дающие в сумме 0):(x↵)(x2↵21) = (x + 2↵) · (x + ↵ + 2) == x + ↵x + 2x + 2↵x + 2↵2 + 4↵ == x2 + 2x + 2↵ + 2 + 4↵ = x2 + 2x + 2.Построенное расширение � поле 3 [x]/(x2 + 2x + 2) �содержит найденный ранее корень 2, поэтому многочлен f (x) вэтом поле раскладывается на следующие линейные множители:f (x) = x3 + x + 2 = (x 2)(x ↵)(x 2↵(x + 1)(x + 2↵)(x + ↵ + 2).1) =Прикладная алгебраПоля ГалуаЗадачи147 / 432Решение (продолжение -3)4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
