Лекции по прикладной алгебре. v2.0 (1127112), страница 10
Текст из файла (страница 10)
. . = (2a + 6b)x + (6a + b) = 16a + b = 1a=1⇒a + 3b = 0b=2Проверка: (6x + 1)(x + 2) = 6x2 + 13x + 2 = 1 + 7x = 1.Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-13)Найти порядок элемента x + x2 в мультипликативной группе12F2 [x]/(x4 + x + 1);поля F2 [x]/(x4 + x3 + 1).поля124 / 432Прикладная алгебраПоля ГалуаЗадачи124 / 432Задача (ПГ-13)Найти порядок элемента x + x2 в мультипликативной группе12F2 [x]/(x4 + x + 1);поля F2 [x]/(x4 + x3 + 1).поляРешениеx + x2 = x(x + 1)1x4 = x + 1(x2 + x)2 = x4 + x2 = x2 + x + 1,(x2 + x)3 = x(x + 1)(x2 + x + 1) = x(x3 + 1) == x4 + x = x + 1 + x = 1.Ответ: 3.Прикладная алгебраПоля ГалуаЗадачи2125 / 432x4 = x3 + 1(x2 + x)2 = x4 + x2 = x3 + x2 + 1,(x2 + x)3 = x(x + 1)(x3 + x2 + 1) = x(x4 + x2 + x + 1) == x(x3 + x2 + x) = x4 + x3 + x2 = x2 + 1,(x2 + x)4 = (x2 + x)(x2 + x)3 = (x2 + x)(x2 + 1) == x4 + x2 + x3 + x = x3 + 1 + x2 + x3 + x == x2 + x + 1,...Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-14)Найти количество неприводимых многочленов123степени 7 над полем F2 ;степени 6 над полем F5 ;степени 24 над полем F3 .126 / 432Прикладная алгебраПоля ГалуаЗадачи126 / 432Задача (ПГ-14)Найти количество неприводимых многочленов123степени 7 над полем F2 ;степени 6 над полем F5 ;степени 24 над полем F3 .РешениеPmdm = pnm|n1d7 =?Pmdm = 27 = 1 · d1 + 7 · d7 = 128.m|7d1 = 2 (x, x + 1) ⇒ d7 = (128 − 2)/7 = 126/7 = 18.Прикладная алгебраПоля ГалуаЗадачи127 / 432Задача (ПГ-15)Чему равно произведение всех ненулевых элементов поляF62 ?Прикладная алгебраПоля ГалуаЗадачи127 / 432Задача (ПГ-15)Чему равно произведение всех ненулевых элементов поляF62 ?РешениеВсе ненулевые элементы поля6 −1x2F62 являются корнями уравнения− 1 = x63 − 1 = 0 .По теореме Виета их произведение равно свободному члену,т.е.
−1 ≡2 1.(∗)Прикладная алгебраПоля ГалуаЗадачи128 / 432Задача (ПГ-16)Чему равна сумма всех элементов поляF73 .Прикладная алгебраПоля ГалуаЗадачи128 / 432Задача (ПГ-16)Чему равна сумма всех элементов поляF73 .РешениеВсе элементы поляF73 являются корнями уравнения7x3 − x = x2187 − x = 0 .(∗)По теореме Виета их сумма равна коэффициенту перед x2186 ,т.е.
0.Прикладная алгебраПоля ГалуаЗадачи129 / 432Задача (ПГ-17)Для поля F23 = F3 [x]/(−2x2 + x + 2) построить таблицусоответствий между полиномиальным и степеннымпредставлением для ненулевых элементов.С помощью данной таблицы вычислить выражение(2x)7 (2)1−.2x + 1 (x)9 (x + 2)Прикладная алгебраПоля ГалуаЗадачи129 / 432Задача (ПГ-17)Для поля F23 = F3 [x]/(−2x2 + x + 2) построить таблицусоответствий между полиномиальным и степеннымпредставлением для ненулевых элементов.С помощью данной таблицы вычислить выражение(2x)7 (2)1−.2x + 1 (x)9 (x + 2)Решениеchar F23 = 3, поэтому −2x2 + x + 2 ≡3 x2 + x + 2 = f (x).Прикладная алгебраПоля ГалуаЗадачи129 / 432Задача (ПГ-17)Для поля F23 = F3 [x]/(−2x2 + x + 2) построить таблицусоответствий между полиномиальным и степеннымпредставлением для ненулевых элементов.С помощью данной таблицы вычислить выражение(2x)7 (2)1−.2x + 1 (x)9 (x + 2)Решениеchar F23 = 3, поэтому −2x2 + x + 2 ≡3 x2 + x + 2 = f (x).2F2∗3 содержит 3 − 1 = 8 элементов и все они могут бытьпредставлены как степени αi , i = 1, 8 примитивного элемента α.Прикладная алгебраПоля ГалуаЗадачи129 / 432Задача (ПГ-17)Для поля F23 = F3 [x]/(−2x2 + x + 2) построить таблицусоответствий между полиномиальным и степеннымпредставлением для ненулевых элементов.С помощью данной таблицы вычислить выражение(2x)7 (2)1−.2x + 1 (x)9 (x + 2)Решениеchar F23 = 3, поэтому −2x2 + x + 2 ≡3 x2 + x + 2 = f (x).2F2∗3 содержит 3 − 1 = 8 элементов и все они могут бытьпредставлены как степени αi , i = 1, 8 примитивного элемента α.Если элемент x окажется примитивным, то положим α = x и,поскольку вычисления в F23 проводятся по mod f (x), будем иметьx2 + x + 2 = 0 ⇒ x2 = −x − 2 = 2x + 1.Прикладная алгебраПоля ГалуаЗадачиРешение (продолжение;130 / 432x2 = 2x + 1)x2 = 2x + 1 ,x3 = x · x2 = x(2x + 1) = 2x2 + x = 2(2x + 1) + x = 2x + 2 ,x4 = x · x3 = x(2x + 2) = 2x2 + 2x = 2(2x + 1) + 2x = 2 ,x5 = x · x4 = 2x ,x6 = x · x5 = 2x2 = 2(2x + 1) = x + 2 ,x7 = x · x6 = x(x + 2) = x2 + 2x = 2x + 1 + 2x = x + 1 ,x8 = (проверочка) x · x7 = x(x + 1) = x2 + x = 2x + 1 + x = 1 .— т.е.
x — примитивный элемент (повезло, иначе его пришлось быискать);Прикладная алгебраПоля ГалуаЗадачиРешение (продолжение;130 / 432x2 = 2x + 1)x2 = 2x + 1 ,x3 = x · x2 = x(2x + 1) = 2x2 + x = 2(2x + 1) + x = 2x + 2 ,x4 = x · x3 = x(2x + 2) = 2x2 + 2x = 2(2x + 1) + 2x = 2 ,x5 = x · x4 = 2x ,x6 = x · x5 = 2x2 = 2(2x + 1) = x + 2 ,x7 = x · x6 = x(x + 2) = x2 + 2x = 2x + 1 + 2x = x + 1 ,x8 = (проверочка) x · x7 = x(x + 1) = x2 + x = 2x + 1 + x = 1 .— т.е.
x — примитивный элемент (повезло, иначе его пришлось быискать); теперь вычислим значение выражения ( 28 = 256 ≡3 1):1x7x8 x7 x81(2x)7 (2)−=−=− 15 =2x + 1 (x)9 (x + 2)x2 x9 x6x2x6= x − 1 = x + 2 − 1 = x + 1.Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-18)Для поля F23 = F3 [x]/(x2 + 1) построить таблицу соответствиймежду полиномиальным и степенным представлением для всехненулевых элементов поля.131 / 432Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-18)Для поля F23 = F3 [x]/(x2 + 1) построить таблицу соответствиймежду полиномиальным и степенным представлением для всехненулевых элементов поля.РешениеВ данном поле x2 + 1 = 0 ⇒ x2 = −1 ≡3 2.1.
Найдём порядок элемента x ⇒ проверим степени,являющиеся делителями 32 − 1 = 8, т.е. 2 и 4:131 / 432Прикладная алгебраПоля ГалуаЗадачи131 / 432Задача (ПГ-18)Для поля F23 = F3 [x]/(x2 + 1) построить таблицу соответствиймежду полиномиальным и степенным представлением для всехненулевых элементов поля.РешениеВ данном поле x2 + 1 = 0 ⇒ x2 = −1 ≡3 2.1. Найдём порядок элемента x ⇒ проверим степени,являющиеся делителями 32 − 1 = 8, т.е.
2 и 4:x2 = 2, x4 = 1.Следовательно, элемент deg x = 4 и x не являетсяпримитивным элементом. Также не являются примитивнымивсе степени элемента x: x2 = 2, x3 = 2x, x4 = 1.Прикладная алгебраПоля ГалуаЗадачиРешение (продолжение)2. Найдём порядок элемента x + 1:(x + 1)2 = x2 + 2x + 1 = 2x, (x + 1)4 = (2x)2 = 2,т.е. x + 1 оказался примитивным элементом.132 / 432Прикладная алгебраПоля ГалуаЗадачи132 / 432Решение (продолжение)2.
Найдём порядок элемента x + 1:(x + 1)2 = x2 + 2x + 1 = 2x, (x + 1)4 = (2x)2 = 2,т.е. x + 1 оказался примитивным элементом. Его степени:α = x + 1,α5 = 2(x + 1) = 2x + 2,α2 = 2x,α6 = α2 · α4 = x,α3 = 2x(x + 1) = 2x + 1,α7 = x(x + 1) = x + 2,α4 = (α2 )2 = 2,α8 = (α4 )2 = 1.Прикладная алгебраПоля ГалуаЗадачи132 / 432Решение (продолжение)2. Найдём порядок элемента x + 1:(x + 1)2 = x2 + 2x + 1 = 2x, (x + 1)4 = (2x)2 = 2,т.е.
x + 1 оказался примитивным элементом. Его степени:α = x + 1,α5 = 2(x + 1) = 2x + 2,α2 = 2x,α6 = α2 · α4 = x,α3 = 2x(x + 1) = 2x + 1,α7 = x(x + 1) = x + 2,α4 = (α2 )2 = 2,α8 = (α4 )2 = 1.Заметим, что вычисление очередной степени αi+j часто бываетудобным провести как αi · αj , а не как α · αi+j−1 .Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-19)В факторкольце F3[x]/(x4 + 1) найти все элементы главногоидеала x2 + x + 2 .133 / 432Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-19)В факторкольце F3[x]/(x4 + 1) найти все элементы главногоидеала x2 + x + 2 .Решение1.
Сначала проверим, является ли многочленf (x) = x2 + x + 2 делителем x4 + 1?133 / 432Прикладная алгебраПоля ГалуаЗадачи133 / 432Задача (ПГ-19)В факторкольце F3[x]/(x4 + 1) найти все элементы главногоидеала x2 + x + 2 .Решение1. Сначала проверим, является ли многочленf (x) = x2 + x + 2 делителем x4 + 1?x4 + 1 = (x2 + x + 2) · (x2 + 2x + 2) — да!Поэтому искомый идеал составят многочлены кольца (т.е.степени не выше 3), кратные f (x):x2 + x + 2 = (x2 + x + 2) · (ax + b) | a, b ∈ F3 .Проведём умножение:(x2 + x + 2) · (ax + b) = ax3 + (a + b)x2 + (2a + b)x + 2b.Прикладная алгебраПоля ГалуаЗадачи134 / 432Решение (продолжение)2.
Теперь, перебирая все возможные значения a, b ∈ F3 , найдём2все элементы идеала x + 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 + 1Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-20)В поле F7 [x]/(x4 + x3 + x2 + 3) найти обратный элемент дляx2 + x + 3.135 / 432Прикладная алгебраПоля ГалуаЗадачи135 / 432Задача (ПГ-20)В поле F7 [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, т.к.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
