Контрольная работа по дискретной математике на тему Дискретная математика: решение комплекса задач

Показать, что многочлен f(x) = x4 + x3 + x2 + x + 1 неприводим над полем F2. Описать поле F16, полученное расширением поля F2 при помощи корня ξ многочлена f(x). Является ли элемент ξ поля F16 примитивным? Найти минимальный многочлен элементов ξ и (ξ^2+〖1)〗^(-1).
Решение:
Многочлен f(x) над полем K приводим, если существуют такие многочлены h(x), g(x) над тем же полем K, такие, что f(x)=h(x)∙g(x) и 0<deg(g), deg(h)<deg(f), т.н. в поле K полином f разлагается на сомножители полиномы над тем же полем меньшей степени и отличные от констант. При этом обязательно выполняется равенство deg(f) = deg(h) + deg(g), т.е. сумма степеней полиномов сомножителей равна степени полинома f, т.е. числу 4. Без ограничения общности можно считать, что deg(h)≤deg⁡(g). Возможны случаи: deg(h) =1, deg(g) = 3 и deg(h) = 2, deg(g) = 2.
Рассмотрим первый случай, т.е. h(x)=α_0∙x+α_1, g(x)=β_0∙x^3+β_1∙x^2+β_2∙x+β_3. Можно считать, что α_0=β_0=1K. Действительно h(x)∙g(x)=(α_0∙x+α_1,)∙(β_0∙x^3+β_1∙x^2+β_2∙x+β_3 )=α_0∙β_0∙x^4+⋯=f(x)=x^4+x^3+x^2+x+1. Приравнивая коэффициенты при x^4, получаем α_0∙β_0=1, отсюда β_0=α_0^(-1). Рассмотрим полиномы h1(x)=α_0^(-1) (α_0∙x+α_1 )=x+α_0^(-1) α_1 и g1(x)=α_0∙(β_0∙x^3+β_1∙x^2+β_2∙x+β_3 )=β_0^(-1)∙(β_0∙x^3+β_1∙x^2+β_2∙x+β_3 )=x^3+β_0^(-1)∙β_1∙x^2+β_0^(-1)∙β_2∙x+β_0^(-1)∙β_3. Тогда h_1 (x)∙g_1 (x)=α_0^(-1) (α_0∙x+α_1 )∙α_0∙(β_0∙x^3+β_1∙x^2+β_2∙x+β_3 )=(α_0∙x+α_1 )∙(β_0∙x^3+β_1∙x^2+β_2∙x+β_3 )=h(x)∙g(x)=f(x), причем многочлены h1(x) и g_1 (x) имеют коэффициенты, равные 1 при старших степенях.
Итак, имеем: h(x)=x+α_1, g(x)=x^3+β_1∙x^2+β_2∙x+β_3 и выполняется равенство:
x^4+x^3+x^2+x+1=(x+α_1 )∙(x^3+β_1∙x^2+β_2∙x+β_3 )=x^4+(α_1+β_1 )∙x^3+(α_1∙β_1+β_2 )∙x^2+(α_1∙β_2+β_3 )∙x+α_1∙β_3
Приравнивая коэффициенты при одинаковых степенях x, получаем следующую систему уравнений в поле F_2={0,1}:
{█(α_1+β_1=1@α_1∙β_1+β_2=1@■(α_1∙β_2+β_3=1@α_1∙β_3=1))┤;
Так как для всех неизвестных коэффициентов α_i,β_j имеется только 2 возможности: 0 или 1, то из последнего уравнения системы автоматически следует, что α_1=β_3=1. Тогда из первого уравнения системы будем иметь 1+β_1=1, откуда β_1=1-1=0. Подставляя этот результат во второе уравнение, получаем α_1∙β_1+β_2=0∙β_1+β_2=β_2=1. Тогда третье уравнение приобретает вид α_1∙β_2+β_3=1∙1+1=1, но 1∙1+1=1+1=0 в поле K=F2, получаем 0=1- противоречие. Итак, случай deg(h)=1, deg(g)=3 невозможен. Рассмотрим случай deg(h)=2, deg(g)=2, т.е. h(x)=x^2+α_1∙x+α_2, g(x)=x^2+β_1∙x+β_2 и имеет место тождество:
(x^2+α_1∙x+α_2 )∙(x^2+β_1∙x+β_2 )=x^4+x^3+x^2+x+1.
Раскрывая скобки и приравнивая коэффициенты при равных степенях х, как и ранее, получаем систему уравнений
{█(α_1+β_1=1@α_1∙β_1+α_2+β_2=1@■(α_1∙β_2+α_2∙β_1=1@α_2∙β_2=1))┤;
Из последнего уравнения α_2=β_2=1.Тогда α_2+β_2=1+1=0. Второе уравнение приобретает вид α_1∙β_1+0=α_1∙β_1=1. Тогда α_1=β_1=1. Первое уравнение приобретает вид α_1+β_1=1+1=0=1, таким образом, и во втором случае deg(h)=2, deg(g)=2 получаем противоречие. Итак, разложение f(x)=h(x)∙g(x) в пространстве полиномов над полем F2={0,1} невозможно, поэтому полином f(x)=x^4+x^3+x^2+x+1 является неприводимым.
Теория:
Теорема 1. Пусть K – расширение поля F, θ∈K- алгебраический элемент степени n над F, M – его минимальный многочлен над F. (В нашем случае F={0,1}, K=C - поле комплексных чисел,θ=ξ- корень полинома M= f(x)=x^4+x^3+x^2+x+1 с коэффициентами из F={0,1}, такой, что f(ξ)=0, полином f(x) минимальный полином для элемента ξϵС, т.е. полином минимальной степени, аннулирующий элемент ξ. Полином f(x) минимальный, т.к. в противном случае он делился бы на минимальный и не был бы минимальным)
Тогда существует изоморфизм ѱ;F[x]/(f(x)) = F16 на поле F2(ξ)- расширение поля F2 на элемент ξ, такой, что ѱ([x])=ξ.. При этом F[x]/(f(x))={[g(x)]_(f(x)) }- множество полиномов степени <=deg(f(x))-1=4-1=3 над F по модулю полинома f(x)=x^4+x^3+x^2+x+1.