Конечные поля
Федеральное агентство по образованию
Государственное образовательное учреждение
высшего профессионального образования
«Южно-Уральский государственный университет»
Кафедра "Прикладной математики"
ОТЧЁТ ПО КУРСОВОЙ РАБОТЕ
по дисциплине «Алгебраические структуры»
Тема: «Конечные поля»
Выполнил: Батаев Д.В.
Челябинск - 2010
Содержание отчета
Формулировка задачи
Решение поставленной задачи
Используемые утверждения и определения
Используемые теоремы
Решение задачи
Список литературы
Приложение 1. Программная реализация
Приложение 2. Теорема Силова
Приложение 3. Теорема о конечных абелевых подгруппах
Формулировка задачи
конечное поле разложение программа
Изучить конструкции и простейшие свойства конечных полей. Построить конечное расширение простого конечного поля. Изучить на примерах конечных полей понятие степени расширения, конструкцию и однозначную определенность поля разложения, простые поля, понятие примитивного элемента, строение конечной мультипликативной подгруппы поля.
- Проверить многочлен на неприводимость над θ.
Получить разложение данного многочлена на неприводимые множители над θ.
- Написать программу, которая позволяет проверить θ на примитивность.
Решение поставленной задачи
Используемые утверждения и определения
Определение 1.
Система элементов называется полем, если выполнены законы:
- Сложение и умножение вполне определены;
Умножение и сложение ассоциативно;
Умножение и сложение коммутативно;
Существует нулевой и единичный элементы;
Существуют противоположные и обратные элементы;
Выполняется дистрибутивность.
Определение 2.
Поле конечно если оно состоит из конечного числа элементов.
Определение 3.
Поле - простое, если оно не содержит собственных подполей.
Определение 4.
Поле K - конечное расширение подполя F, если все элементы поля K - это линейные комбинации конечного множества элементов с коэффициентами из F, то есть . Размерность, то есть число элементов в базисе K - степень расширения K над F.
Определение 5.
Расширение, полученное присоединением одного элемента, называется простым расширением поля.
Определение 6.
Расширение K поля F называется алгебраическим над F, если каждый элемент из K является алгебраическим над F.
Определение 7.
Многочлен неприводим над полем, если его нельзя представить в виде произведения нетривиальных (неконстантных) многочленов.
Утверждение 1.
Для произвольно заданного поля F существует одно (и с точностью до эквивалентности расширений только одно) простое алгебраическое расширение F(θ) такое, что θ является элементом, удовлетворяющим уравнению, где - неразложимый многочлен из F[x].
Используемые теоремы
Теорема 1. О неприводимости многочлена степени 2 или 3.
Для неприводимости многочлена степени 2 или 3 в кольце необходимо и достаточно, чтобы он не имел корней в поле F.
Доказательство
►Если многочлен f не имеет корней в поле F, но приводим в кольце F[x], то его можно записать в виде Но , откуда deg(g)=1. Значит, , где . Но тогда элемент - является корнем многочлена g, а значит, и многочлена f в F, что противоречит предположению. Теорема доказана. ◄
Теорема 2.
Если - неприводимый многочлен степени m, то в поле содержится любой корень многочлена f. Более того, все корни многочлена f просты и ими являются m различных элементов поля .
Доказательство:
►Пусть - произвольный корень многочлена f в поле разложения этого многочлена над . Тогда , так что и, в частности, . Покажем теперь, что если - какой-нибудь корень многочлена f, то - тоже корень этого многочлена. Пусть f записан в виде , где . Применяя лемму 2.3[1] и теорему 1.46[1], получаем
Поэтому элементы являются корнями многочлена f. Остается доказать, что эти элементы различны. Допустим обратное. Тогда для некоторых целых j и k, . Возводя это равенство в степень qm-k получаем .
Из леммы 2.12[1] следует, что многочлен f(x) делит многочлен , а по лемме 2.13[1] это возможно лишь в случае, когда число m делит m-k+j. Но так как 0 < m-k+j < m то мы получаем противоречие. ◄
Следствие к теореме 2.
Если - неприводимый многочлен степени m, то его полем разложения над полем является .
Доказательство:
►Из теоремы 2 следует, что многочлен разлагается в поле и . Но из доказательства теоремы видно что ч.т.д.◄
Решение задачи
1) Докажем, что многочлен неприводим над . По теореме 1 о неприводимости многочлена необходимо и достаточно, чтобы он не имел корней в поле . Покажем это:
(0)=1;f(1)=3;f(2)=1;f(3)=1;f(4)=4;
Корней нет, следовательно, многочлен неприводим над полем .
) Пусть θ корень многочлена . Так как неприводимый многочлен степени n=3 над полем , то, присоединяя к полю корень этого многочлена мы получим конечное поле [θ] из элементов.
По следствию к теореме 2 полем разложения многочлена степени 3 над полем является поле =. А так как поле является конечным расширением поля и @[x]/<f(x)>, где <f(x)> - множество элементов кратных f(x), то, из всего этого следует, что все элементы поля представимы в виде ,где .Разложим многочлен на неприводимые множители из.
Так как θ - корень, далее подставим в многочлен, затем раскроем скобки, возведем в степени и сгруппируем.
Для решения задачи разложения многочлена на множители была написана программа (Приложение 1), последовательно перебирающая элементы поля и подставляющая их в исходный многочлен. Если при подстановке очередного элемента многочлен обращается в ноль, то этот элемент является корнем.
Результат вывода программы:
0Θ^2+1Θ+0
Θ^2+0Θ+0
Θ^2+4Θ+4
Θ^2+4Θ+0
Θ^2+1Θ+1
Θ^2+2Θ+1
Θ^2+0Θ+4
Θ^2+2Θ+3
Θ^2+3Θ+0
Θ^2+3Θ+3
Θ^2+0Θ+2
Θ^2+4Θ+2
Θ^2+2Θ+0
Θ^2+1Θ+1
Θ^2+4Θ+3
Θ^2+2Θ+4
Θ^2+0Θ+1
Θ^2+4Θ+3
Θ^2+3Θ+0
Θ^2+1Θ+1
Θ^2+3Θ+2
Θ^2+1Θ+4
Θ^2+1Θ+2
Θ^2+1Θ+4
Θ^2+3Θ+4
Θ^2+3Θ+4
Θ^2+1Θ+2
Θ^2+4Θ+2
Θ^2+1Θ+4
Θ^2+0Θ+1
Θ^2+0Θ+4
Θ^2+4Θ+0
Θ^2+0Θ+0
Θ^2+1Θ+1
Θ^2+1Θ+0
Θ^2+4Θ+4
4Θ^2+3Θ+4
Θ^2+0Θ+1
Θ^2+3Θ+2
Θ^2+2Θ+0
Θ^2+2Θ+2
Θ^2+0Θ+3
Θ^2+1Θ+3
Θ^2+3Θ+0
Θ^2+4Θ+4
Θ^2+1Θ+2
Θ^2+3Θ+1
Θ^2+0Θ+4
Θ^2+1Θ+2
Θ^2+2Θ+0
Θ^2+4Θ+4
Θ^2+2Θ+3
Θ^2+4Θ+1
Θ^2+4Θ+3
Θ^2+4Θ+1
Θ^2+2Θ+1
Θ^2+2Θ+1
Θ^2+4Θ+3
Θ^2+1Θ+3
Θ^2+4Θ+1
Θ^2+0Θ+4
Θ^2+0Θ+1
#62
Элемент θ порождает 62 элемента, а, следовательно не является примитивным элементом поля .
Список литературы
1. Лидл Р. Нидеррайтер Г., Конечные поля: в 2-х т. - М.: Мир, 1988
2. Ван-дер-Варден Б.Л., Алгебра, М.:Наука, 1976
. Каргаполов М.И. Мерзляков Ю.И., Основы теории групп М.:Наука, 1982
. Холл М., Теория групп, М.: Наука, 1961
Программная реализация
// Программа для нахождения корней многочлена
#include <stdio.h>main(void){q,i,j,k;(int i=0;i<5;i++)
for(int j=0;j<5;j++)
for(int k=0;k<5;k++){((i*i*i+2*i*i*j+2*i*i*k+2*i*j*j+3*j*j*k+3*i*k*k+i)%5)continue;((2*i*i*i+3*i*i*j+2*i*i*k+2*i*j*j+4*j*j*j+4*i*j*k+3*j*k*k+j)%5)continue;((i*i*i+3*i*i*j+4*j*j*j+4*i*j*k+k*k*k+k+1)%5)continue;
printf("%dO^2+%dO+%d\n",i,j,k);
}
return 0;
}
// Программа для проверки элемента на примитивность
#include <stdio.h>j[3]={0,1,0},s[3],i;main(){(i=0; i<124; i++){("%dO^2+%dO+%d\n",j[2],j[1],j[0]);(int k=0;k<3;k++)[k]=j[k];[0]=(s[2]*4)%5;[1]=(s[0]+4*s[2])%5;[2]=(s[1])%5; (!j[0] && j[1]==1 && !j[2])
break;
}0;
}
Приложение 2
Теорема Силова
Необходимые определения и теоремы:
Определение
Говорят, что группа G действует на множестве M, если для каждых элементов определен элемент причем и здесь e - единица группы G. Множество называется орбитой элемента m.
Теорема Лагранжа
Если H подгруппа конечной группы G, то
Формулировка теоремы Силова:
Пусть G - конечная группа, p - простое число.
Существование. Для каждой степени , делящей порядок G, в G существует подгруппа порядка .
Вложение. Если делит порядок G, то каждая подгруппа порядка из G вложена в некоторую подгруппу порядка из G.
Сопряженность. Все силовские p-подгруппы из G сопряжены в G.
Количество. Количество силовских p-подгрупп из G сравнимо с 1 по модулю p и делит порядок G.
Доказательство:
►
- Существование
Пусть - множество всех подмножеств мощности из G. Очевидно, поэтому наибольшая степень p, делящая - это . Если то, очевидно, так что G действует на правыми сдвигами. Пусть - ты орбита, мощность s которой не делится на . Пусть, далее, непосредственно проверяется, что - подгруппа в G, а - правые смежные классы G по. Покажем, что подгруппа имеет требуемый порядок . Обозначим пока, тогда по теореме Лагранжа. Так как наибольшая степень p, делящая s, - это , то t делится на , в частности . С другой стороны, если то, очевидно, поэтому или. Окончательно.
- Вложение
Пусть делит - подгруппа порядка из -класс подгрупп, сопряженных с P элементами из G. Мы знаем, что Если не делится на p, то делится на, а потому по первой части теоремы в существует подгруппа порядка p. Тогда P* - требуемая подгруппа P. Пусть делится на p. Группа P действует на сопряжениями, причем мощности орбит делят , а потому имеют вид Так как имеется по крайней мере одна одноэлементная орбита {P} и делится на p, то найдется и другая одноэлементная орбита {Q}. Это означает, что P нормализует Q, поэтому PQ есть p-подгруппа (учесть, что и расширения p-подгруппы посредством p-подгруппы есть p- подгруппа). Применяя к PQ тот внутренний автоморфизм группы G, который переводит Q в P, мы получим p-подгруппу PP, содержащую P в качестве собственной нормальной подгруппы. Снова по первой части в PP/P найдется подгруппа P*P/P порядка p, тогда P* - требуемая подгруппа.
Из доказанного утверждения следует, что силовские p-группы конечной группы - это в точности подгруппы порядка , где - максимальная степень p, делящая порядок группы.
- Сопряженность
Пусть P - подгруппа порядка из G (в частности это силовская p-подгруппа), а имеет прежний смысл. Надо доказать, что любая силовская p-подгруппа Q из G лежит в . Но Q действует на сопряжениями, причем орбиты имеют снова мощности Так как теперь заведомо не делится на p, то имеется некоторая одноэлементная орбита {P}, т.е. Q нормализует P. Тогда PQ есть p-подгруппа, и ввиду максимальности P, Q имеем Q=PQ=P
- Количество
В обозначениях предыдущего пункта достаточно проверить, что {Q} - единственная одноэлементная орбита. Но если {Q} - другая такая орбита, то QQ является p-группой, отличной от Q, что невозможно.
Теорема доказана.◄
Приложение 3
Теорема о конечных абелевых подгруппах
Необходимые теоремы:
Теорема о базе свободной группы
Пусть - свободная абелева группа конечной степени n, A - её отличная от нуля подгруппа. Тогда A свободна и группы , A обладают соответственно базами и такими, что , и делится на.
Доказательство:
►Пусть и. Возникает матрица. Будем назвать элементарными следующие преобразования строк и столбцов целочисленной матрицы:
- перестановка двух строк;
прибавление к одной строке целочисленного кратного другой строки;
умножение строки на -1 и аналогичные преобразования столбцов.
Пользуясь тем, что для любых целых чисел a, b, отличных от нуля, найдутся такие целые числа x, y, что ax + by = НОД(a, b), обычными рассуждениями линейной алгебры - более точно, теории λ-матриц - можно привести матрицу М элементарными преобразованиями строк и столбцов к виду. Остается заметить, что элементарные преобразования строк соответствуют перходу к другой базе подгруппы А, а элементарные преобразования столбцов - к другой базе группы. Теорема доказана.◄
Формулировка теоремы о конечных абелевых группах
Всякая конечнопорожденная абелева группа G разлагается в прямую сумму циклических подгрупп. Более точно, G разлагается в прямую сумму бесконечных циклических и примарных циклических групп, причем количество бесконечных циклических слагаемых и набор порядков примарных циклических слагаемых в любом таком разложении одни и те же, т.е. являются инвариантами группы G.
Доказательство:
►По условию, группа G изоморфна некоторой фактор -группе свободной абелевой группе конечной степени n. Согласно теореме о базе свободной группы в группах и A существуют такие базы и , что . Покажем что - прямая сумма циклических подгрупп .
Прежде всего, ясно, что порождается этими подгруппами. Далее, пусть нуль фактор -группы имеет запись . Тогда . С другой стороны, выражая элемент a через базу подгруппы A и учитывая равенства приходи к соотношениям. В виду однозначности записи элементов через свободные порождающие получаем Но это означает, что каждые элемент из элементов принадлежит A. Тем самым доказана однозначность представления нуля в виде суммы элементов подгрупп и, значит, разложимость группы G в прямую сумму циклических подгрупп. Докажем инвариантность чисел. Зафиксируем какое-нибудь разложение группы G в прямую сумму бесконечных циклических и примарных циклических слагаемых и обозначим через и прямые суммы бесконечных циклических и циклических p-слагаемых этого разложения соответственно, где p-простое число. Понятно, что - максимальная p-подгруппа, а - максимальная периодическая подгруппа группы G, так что подгруппа и все не зависят от выбранного разложения. Так как число бесконечных циклических слагаемых равно, то оно - инвариант группы G. Далее, число циклических слагаемых в разложении группы совпадает с таким же числом для её нижнего слоя и, значит, с размерностью векторного пространства над полем из p элементов, а потому - тоже инвариант. Наконец, пусть и, для определенности, Индукцией по докажем, что числа не зависят от выбора разложения. В самом деле, поэтому по индуктивному предложению, те из чисел, которые, - инварианты разложения. Так как количество остальных - это разность между s и количеством чисел , то оно - также инвариант группы.
Теорема доказана.◄