Главная » Просмотр файлов » С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра

С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136), страница 6

Файл №1127136 С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра) 6 страницаС.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136) страница 62019-05-11СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

.м. дл.я эле.мептатак;оui чтоf ((3)=== О . Тогдаполе(3 i а f (х) f (х) делитсяГалуа.м'ногочлепна mrз (х).Доказательство. Разделимf(x)===u(x) · mrз (x)f (x) на mrз (x) с остатком :+ v(x), О ~ degv < degmrз (x) .Подставляя в это равенствоО ===f ((3)===(3вместо х, получаемu(f3) mrз ((3) +v ((3)"V'===v ((3) ,",1=0т. е .(3 -mrз (x) икореньv(x), чтопоэтому v(x)противоречит минимальностиО.о2.4.(IIIпоток) Конечные поля57Сле ствие. Дл.я паждог о элемента пол.я существуетне более одного м.м.Доказа тельс тво . Пусть минимальных многочленов два.Они взаимно делят друг друга, а значит, различаютсяна обратимый множитель-константу.Поскольку минимальный многочлен нормирован,эта константа равнат. е.

данные многочлены совпа­1,дают.оУтве ж ение2.7 . Дл.я к;аждого эле.ме?-tта {3 пол.я IF~существует .м ..м .дитn: deg т{З(х)m f3 (х)~ n.и его степепъ не превосхо­Доказа тельство . Рассмотрим следующие элементы поляIF~: 1, {3, {32, . . . ,{3п - их n+ 1 штук , а размерность IF~как векторного пространства равнаn=?эти элементылинейно зависимы, т. е . существуiGТ такие не все равныеО коэффициенты со,=?... , Сп, чтосо 1 + с1fЗ + .

. . + cnf3n == О,{3 - корень многочлена f (х) == са + с1 х + . . . + CnXn .Минимальным многочленом для {3 будет некоторыйнормированный неприводимый делительf (х).Далее будут доказаны ещё два свойства м.м.элемента{3m f3 (x)поля IF~:1.ffi(3 ( Х)2.Многочлен(хРп рсо{3Р2Х) .минимальный{3Pdegm13(x)-1{3 ' rз '' ...'{3 элементов IF~.для••с оnр.яж еn н ъtхГлава58Конечные поля2.Свойства многочленов над конечным полемПоле разлоDfсепи.я мпогочлепаменьшеерымf (х)1r;, n == minf(x)Ер асширение поля!Fp[x] !Fр,наи­над кото­разлагается в произведение линейных мно­жителей .Тео ема 2.4 (о поле разложе ния). Любой ненулевоu эле­мент пол.яxPn - l -F1r;==.явл.яетс.я гк;орпем многочлена1:n_ lхР-1 == ( Хгде { (31 , ...

, /3рп_ 1==}fЗ1 )-· . . . · (Х-(Зрп -l)F* , т. е. F - поле разложенияданного многочлена.Доказател ь ство .F * - циклическая групп а по ум ноже­нию порядка pn - 1.Порядок ord а любого её элемента (== порядок цик­лической подгруппы (а)-по теореме Лагранжа) де­лит порядок группы .П оэтомуapn- 1 _1==pn - 1 == q · ord aaqoгda _1т.

е . а- корень xPn - l -==и(aoгda)q _1о,1.DСле ствие (тео рем а Фе рм а ) . Все элемепты пол.я1r;, nenисгк;люча.я нул.я, .явл.яютс.я гк;орн.ями мпогочлепа хР - х.Доказательство. Вынесем х за скобку:хРп -Х == Х ( хРп - l -1) .У второго сомножителя корнями будут все неиулевыеэлементы поля, а у первогоИными словами ,nхP-х.1r; --О.ополе разложения м ногочлена2.4.(IIIТео ем апоток) Конечные поля2о 5 о59В rх;олъце .многочленов над rх;онечны.м полем••(xn- 1) : (xm- 1) {::} n :т.Доказа тел ьство.•Пустьn ==тk . Сделаем заменуxm ==у, тогдаxn - 1 == yk - 1 и xm - 1 == у - 1.Делимость очевидна, т. к .

1 - корень yk - 1.••Предположим, чтоО<r <П оследнее/т, т.е.nn == km+ r,т, тогдавыражениезадаетрезультатделенияxn- 1 на xm- 1 с остатком, поскольку xmk- 1 делит­ся на xm - 1 по доказанному выше.О статок xr - 1 =/= О в силу сделанных предположений .С ледовательно xn - 1 не делится на xm - 1.оТеорема даёт возможность раскладывать многочле­ныxn - 1при составныхn.Пример 2.12. Многочлен х 1 5 + 1 Е lr 2 [x] (гдедолжен делиться на х 3 + 1 и х 5 + 1.- 1 == + 1)Действительно,х15312+ 1 ==(х + 1 )(х5109+х +х +х + 1 )56== (х + 1) (х + х + 1).360Глава 2.

Конечные поляТео ем а2.б . Все веприводимые .многочле 'Н/Ы n-u cme'-'nпени из rFp[x] дел.ят многочлен хР-х.Доказательство .n ~ 1. Убеждаемся , что (х-а)(хР- х), где а Е [FP:поскольку аР ~ а, оба дан н ых многочлена имеюткореньn> 1.а.В ыбираем неприводимый нормированный м ного­f (х)членустепенино!1 ) и строим полеиз [FР [n] (пока не доказа­n[Fр[х]/ (f(x)).В нём х- корень и своего м . м . f(x) , и xPn- 1 - 1.По свойствам м . м . xPn- l- 1 делится на f(x) .DПример2.13 (продолжение Примера 2. 12) .

Продолжаемразложение х 1 5 + 1 Е [F 2 [х] .4Поскольку 15 ~ 2 -1 , все неприводимые многочле­16ны 4-й степени будут делителями х - х и , следова­тельно, х 15 + 1. Таких многочленов 3:443432х + х + 1, х + х + 1 и х + х + х + х + 1.И меем153443432х + 1 ~ (х + 1 )(х +х+ 1 )(х +х + 1 )(х +х +х +х+ 1 ).Замечаем , что 3 ~ 2 - 1, и поэтому все неприводи­4мые многочлены 2-й степени будут делителями х - х3и , следовательно, х + 1. Такой многочлен только один :2х + х + 1.Окончательно получаем разложение х 1 5 +1 на нераз­2ложимые над [F 2 многочлены:1Теорема 2.12.4.хпоток) Конечные поля(III15612+ 1 == (х + 1)(х + х + 1) хх (х + х + 1) (х + х + 1) (х + х + х + х + 1).443432Тео ема 2. 7. Любоu кеприводи.мыu де.л.ящиu xPn .мкого'Lt.лек имеет степекъ, ке превосход.ящуюДоказа тельс тво.xPn -х степениТогда FП устьерk.!Fр/ (ер) -defхk- lОбозначим химеем аРn- а==n.н еприводимый делительполе, которое рассмот-рим как векторное пространство над1' -х, . .

. 'х!FРс базисом.==а. Посколькуn.(хР - х) : ер, то в FО.Любой элементFвыражается через базис:k- lf3 ==Laiai .i=OВозведя обе части этого равенства в степеньчимk- lf3Pn ==Lf3 -полу-k- lLai a ii= Oт. е .pn,ai a i== /3,i=Oкорень уравненияхpn-х_ О-Итак , каждый элемент поляF является корнем ( *) ,но у ( *) не более pn различных корней, а F == pk;п оэтому n ;? k.о62ГлаваИтак,f(x)вопрос:Екакиеделят хР!F[x]Ответ: либоn-2.

Конечные полявеприводимыемногочленых?- степени n , либо (2) некото­рый - степени < n и (3) других нет.(1)л1обойСледующая теорема позволяет находить все корнимногочлена, если известен какой-либо корень известен :достаточно возводить его последовательно в степени р .Тео ема 2.8 (свойство корней неприводимого мно­гочлена). Если f3 %оре'Нъ 'Неnриводи.мо го .м'Ногочле'Настеnе'НиJ(x)p(3Р2f3 , f3 ,,(ЗРп- 1... ,изn!Fp[x] ,исчерпываюттосписо%эле.ме'Нтывсехnег оnop'Нeu .Доказательство.f (х),то (ЗР-l.Покажем , что еслиf3 -кореньтоже корень .П оскольку аР==а для всех а Е!Fр,то справедливо(ао + а1х + ...

+ akxk)P ==+ afxP + а~х Р + ... + a~Xkp ==== ао + а1 (хР) + а2(хР) + ... + ak(xP)k,2аь2т. е . для любого многочлена ср(х) Е!Fp[x]выполняетсяраве н ство( <р ( х) ) РОтсюдаJ(/3) ==1О==<р ( хР) .{::} J(f3)P ==(*){::} J(f3P) ==ОО иf3, (ЗР, ... , (ЗРп- - корни многочлена f (х).2. Осталось доказать, что все f3, (ЗР, ...

, (ЗРп- раз­1личны , и тогда (многочлен степениnnимеет не болеекорней) можно утверждать , что найдены все корнимногочленаf (х).2.4.поток) Конечные поля(IIIl==Пр едположим, что (ЗР(ЗР63k,считая~lk.Далее ,по скольку(ЗРто (3 -корень уравненияП о Теоремет. е .l == kрk==xPn- k+l _1 -2.6 получаем n - k1==+lО.~~nl~k,и все вышеописанные корни р азличны .Корничленаn-k(3,f (х)(ЗР, (ЗР2степениn- l(ЗР, ... ,nовеприводимого много-называi{)Т сопр.яже:нны.ми и яс­но, что они лежат в полеrFp[x]/ (f (x)).Нахождение корней неприводимого многочленаПр имер2.14.1.м ногочл е н аН айти корни неприводимого надf( x) == х4lF2+ х + 1.3Решение.

Один корень получаем немедленно : это х .П о только что доказанной теореме можно выписатьостальные корни в поле2х ,4х == х3+ 1,lF2[x]j(j(x)) :8х == х6+1Покажем, что, например, х 2 -==х32+ х + х.действительно ко­рень f(x) : поскольку f(x ) == х + х 3 + 1 хнх 2 == х 8 +2686х + 1 и х == х + 1, то f (х ) == О.22. Решить4уравнениеО,f( x)ЕlF2[x] .Глава642.Решение. Убеждаемся , что многочлендим в1F2 [x] . Поэтому один его корень -Конечные поляf( x)неприво­х, и по доказан­ной теореме выписываем остальные в поле [F 2 [х] / (f (х)) :Покажите самостоятельно, что х 3реньдействительно ко­т. е. чтоf(x),3.

Решить-ур авнение2f( x) = х + 2х- 1 = О , где f( x) Е 1Fз[х] .Решение. Перебором элементов хубеждаемсяf( x) -Е 1Fз ={О,1, 2}веприводимый многочлен.2Но тогда в поле 1F3 [x]/ (х + 2х + 2) он имеет корни х3и х .Поскольку х 2 = -2х3+1=х+ 1, тох = х + х = 2х + 1.Убедимся, что 2х2f( x +x)=2+1-корень2( 2х+ 1) +х+ 1f( x) :=2= х + х + 1 + х + 1 = 3 · (х + 1) = О.2Ответ: многочлен f(x) = х + 2х- 1 Е 1Fз[х] имеет2корни х и 2х + 1 в поле [F3 [x]/ (х + 2х + 2).2.4.(IIIпоток) Конечные поляАлгоритмf(x)Енахождениявсех65корнеймногочленаlrp[x].f (х)1.

Разложитьна неприводимые произведе­ние неприводимых многочленов:f (х)==91 (х) . 92 (х) . .... 9k (х) .2. Для каждого многочлена 9i (х), i == 1, k рас­смотреть расширение lrp [x]/(9i (x)), в которомон будет иметь deg 9i корнейра,а,р2а, ... ,pdeg g,i - lа.3. Объединить все корни в одном общем расшире­нии rr;, где n == н ок ( n1, . .. ' nk ).Пр имер2.15. 1.Решить уравнение4f(x) == 2х + х + 4х + 4 == О, где f(x) Е lrs[x].Решение.х32Вычисляемf (х)значениядлявсехЕlr 5 == {0, 1, 2, 3, 4 }: f( O) == 4, f( 1) == 1'f(2) == О и т. о .

х == 2 - корень f(x).Деля << уголком >> f(x) на f 1 (х) == х - 2 == х + 3,4233получим2х +х +4х +4 == (х+3) · (2х +4х+3) .Для удобства нормируем частное 2х + 4х + 3 : т.к.132- == 3, то вместо уравнения 2х + 4х + 3 == О можно3решать уравнение3f 2 (x) == 3 · (2х +4х + 3) == х + 2х + 4 == О .Перебором элементов х Е [Г 5 -366Глава2. Конечные поляf(O) == 4, f(1) == 2, f(2) == 1, f(3) == 2, f(4) == 1,3убеждаемся , что f 2 (x) == х + 2х + 4 - неприводимыймногочлен 2 .В поле [Г 5 [х] 1(х 3 + 2х + 4)255!2(х) == О будут х, х , х .корнями многочлена== -2х- 4 == 3х + 1:22253х == х (3х + 1) == 3х + х == 4х + 3 + х ==2== х + 4х + 3;х25 == (х5)5 == (х2 + 4х + 3)5 == xlO + 45х5 + 35 ==102102== х + 4(х + 4х + 3) + 3 == х + 4х + х .Вычисляем - с учётом х 31055(поскольку 4 == 2 == 1021 и 3 == 81 · 3 == 24~) .Найдём отдельно х 10 :xlo == (х5)2 == (х2 + 4х + 3)2 ==42223== х + х + 3 + 3х + 4х + х ==432== х + 3х + 2х + 4х + 4 ==22==:Ух + ~+ ~х + 3+ 7х + 4х + 4 == 4х + 2.Продолжаем:х251022== х + 4х + х == ~х + 2 + 4х + ~ == 4х + 2.4322Ответ: уравнение f (х) == 2х + х + 4х + 4 == О , где22f(x) Е IF5[x] имеет корни 2, х, х +4х+3, 4х +2 в поле3[F == IF 5 х] х + 2х + 4) (поскольку корень 2 Е F ).1(2.Решить уравнение8j(x) == х + х + х + х + 1 == 0, где j(x) Е [Г2[х] .242а если бы это был многочлен 4-й степени?2.4.(IIIпоток) Конечные поляРешение.67В таблицах веприводимых многочленов дан­ный многочлен отсутствует.Подбором находим, чтоведение двух веприводимых над842х +х +х +х+ 1 == (х4"f 1 ( х)Уравненияразлагается в п роиз­f(x)IF 2 многочленов:34+ х + 1) · (х + х + х + х + 1) .2""vfl(x)== О и3f 2 ( х)== О ранее были реше­ны: их корни соответственн о суть23х, х , х2332+ 1, х + х + хв поле F 1 == IF 2 [х] 1(х43+ х + 1)их, х , х , х32+х +х+1в поле F 2 == IF 2 [ х] 1(х4Степени обоих расширений поля32+ х + х + х + 1) .GF(2)совпадаюти поля F 1 и F 2 изморфны (пока не доказано!),т.о .

все 8 корней уравнения f (х) == О лежат в поле(==4)GF(24).Для запи си данных корней выберем представлениеF 1 поля GF(2 4 ) . Тогда запись корней 1 (x) == О оста­нется без изменений , а корни 2 ( х) == О надо предста­ffвить как элементыF 1.Приравнивая многочлены,порождаiQЩИе данныеполя, получим43х +х + 1 == х +х +х +х+ 1Ясно,432что при подстановкех~х+1 получен­ное равенство останется справедливым . Пр именим дан­ную постановку для изоморфного п реобразования по­лейF1 н F 2.68Глава2.Конечные поляНаходим представления корней многочленаf 2 (x)вполе F1:х ~ х+ 1,2х ~ (х2+ 1) === х + 1,2333х ~ ( х + 1) === х + х + х + 1,22233х + х + х + 1 ~ (х + х + х + 1) + (х + 1)+2+ (х + 1) + 13х .:=:2Удостоверимся, что, например , х + 1 - корень f( x):f(x2+ 1)2(х + 1) +(х + 1) + (х + 1) +(х + 1)+ 1===28===(х162416+ 1) +43(х82+ 1) +82(х4+ 1) + х32===.6Очевидно х === х , х === х + 1 и х === (х + 1) === х + 1.453Поскольку х === х + х === х + х + 1, то22264383х === х + х + х === х + х + х + 1 и х === х + х + х .2Подставляя в выражение для f (х + 1) полученные2полиноми альные представления степеней х, получи м2f (х + 1)3=== ( х232+ 1) + (х + х + х + 1) + х + х === О.Ответ: многочлен f( x) === х 8 + х 4 + х + х + 1 Е IF 2 [x]333имеет корни х, х , х + 1, х , х + 1, х + х + х,343х+ 1 , х +х +х+ 1 в поле IF 2 [x]/(x +x + 1).222223.Н айти корень многочленаf(x)===х4+ 2х + 2===О Е IFз[x].Решение.

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

Тип файла
PDF-файл
Размер
32,22 Mb
Тип материала
Высшее учебное заведение

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

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6553
Авторов
на СтудИзбе
299
Средний доход
с одного платного файла
Обучение Подробнее