AOP_Tom2 (1021737), страница 129
Текст из файла (страница 129)
Поэтому будем рассматривать более общую ситуацию, когда алгебраическая система коэффициентов 5 представляет собой область единственнигв разложения иа множители и не обязана быть полем. Это означает, что 5 — коммутативное кольцо с единицей и что 1) ив ф О, если и и и — ненулевые элементы Я; й) каждый ненулевой элемент и е Я либо обратим, либо имеет "единственное" представление в виде произведения вросших рм ..., р~.' (2) и=р,...рм г) 1.
Обратимый элемент в данном случае представляет собой элемент, который имеет обратную величину, а именно — элемент и, такой, что ии = 1 для некоторого и Е о'. Простой элемент- — это не являющийся обратимым элемент р, такой, что уравнение р = дг истинно только тогда, когда либо д, либо г представляет собой обратимый элемент. Представление (2) единственно в том смысле, что если рг...рг = д1 йо где все р и д просты, то з = г и имеется перестановка я1... т множества (1,..., Ф), такая, что р| = а1а„,, ..., рг — — агд„, для некоторых обратимых ам ..., оэ.
Другими словами, разложение на простые множители единственно с точностью до порядка множителей и до умножения на обратимые. Любое поле представляет собой область единственного разложения на множители, в которой каждый ненулевой элемент обратим и в которой не существует простых элементов. Целые числа образуют область единственного разложения, в которой обратимые элементы — +1 и — 1, а простые — х2, хЗ, х5, х7, х11 и т. д. Случай., когда о' содержит все целые числа, принципиален, поскольку зачастую предпочтительнее работать с целыми коэффициентами, а не с произвольными рациональными. Одним из ключевых фактов, связанных с полиномами (см. упр.
10), является то, что полиивмм над областью единственного разложения образуют область единственного разложения. Поливом, который является простым в этой области, обычно называется неприввдиммм, Многократно используя теорему о единственности разложения, можно доказать, что полиномы от нескольких переменных нзд множеством целых чисел или над любым полем с любым числом переменных могут быть единственным образом разложены на неприводимые полиномы. Например, полинам от трех переменных 90хэ — 120хгу + 18хгуг — 24хугг над целыми числами представляет собой произведение пяти неприводимых полиномов 2 3 х.
(Зх — 4у) . (5х + ух). Тот же полипом над рациональными числами является произведением трех неприводимых полиномов (бх) . (Зх — 4у) (5х + уг). Это разложение может быть записано как х (90х — 120у) ° (х+ -'уг) и еще бесконечным числом способов, хотя разложение, по существу, единственно. Как обычно, мы говорим, что и(х) крашен полиному в(х), а е(х) является делителелг и(х), если и(х) = о(х)д(х) для некоторого полинома д(х). Если есть алгоритм, который определяет, является ли и кратным о для произвольных ненулевых элементов и и о некоторой области единственного разложения Я, и позволяет определить ю, если и = и ю, то алгоритм 1л дает метод для выяснения, является ли и(х) кратным о(х) для произвольных ненулевых полиномов и(х) и о(х) над о.
Если и(х) кратно в(х), легко увидеть, что и„аг должно быть кратно о„при переходе к шагу 02; отсюда будет найдено частное и(х)/о(х). Применяя это наблюдение рекурсивно, получим алгоритм, который ага~чает на вопрос, является ли данный полинам над о от любого числа переменных кратным другому полиному над Я, а также алгоритм, который будет находить частное, если таковое существует. Множество элементов области единственного разложения называется взаилгнв простмлг, если нет простого элемента этой области единственного разложения, который делит все остальные элементы.
Полинам над областью единственного разложения называется примитивным, если его коэффициенты взаимно просты (не путайте это понятие с совершенно другим понятием приминшвнмх полиномов по модулю р, которое обсуждалось в разделе 3.2.2). Следующий факт, представленный лля полиномов нэд целыми числами К. Ф, Гауссом (С. Г. Папээ) в 42 разделе его знаменитой книги Иэцшэйюпеэ Агй)нпебсю (Ье1рг1я, 1801), имеет первостепенную важность. Лемма С (Лемма Гаусса). Произведение примитивных полнномов нал областью единственного разложения примитивно. Доказательство.
Пусть и(х) = и х'"+. +ио и о(х) = и„х" + +ие — -примитивные полиномы. Пусть р — любой простой элемент области; тогда следует показать, что р не делит все коэффициенты и(х)с(х). По условию имеется такой индекс у, что иу не делится на р, и такой индекс к, что иь не делится на р. Пусть у и й— наименьшие такие индексы: тогда коэффициент при хэ+ в и(х)и(х) равен иэиь + и,+гол г + + из+с ио + иу г И+1 + . + иоиь+л Так как первый член этой суммы не делится на р, а все остальные делятся, на р не делится и вся сумма.
г Если ненулевой полинам и(х) над областью единственного разложения 5 не примитивен, можно записать и(х) = рг иг(х), где рг — простой элемент из 5, делящий все коэффициенты и(х), а и1(х) — другой ненулевой полинам над 5. Все коэффициенты иг(х) имеют на один простой множитель меньше соответствующих коэффициентов и(х). Теперь, если иг(х) не примитивен, можно записать иг(х) = рг иг(х) и т. д.
Этот процесс безусловно прекратится при представлении и(х) = с иь(х), где с й 5 и иь(х) — примитивен. Фактически имеется соответствующая лемме С лемма Н. Лемма Н. Любой ненулевой полянам и(х) над областью единственного разложения 5 можно разложить нв множители в виде и(х) = с и(х), где с представляет собой элемент 5, а и(х) — примитивный полинам. Кроме того, это представление единственно в том смысле, что если и = сг ог(х) = сг ° иг(х), то с, = асг н иг (х) = аиг (х), где а — обратимый элемент 5.
Докаэательсгпво. Мы уже показали, что такое разложение существует, так что доказательства требует только единственность разложения. Положим, что сг ° иг (х) = сг ег(х), где иг(х) и ег(х) — примитивные полиномы. Пусть р — некоторое простое из 5. Если р" делит сы то оно делит и сг, в противном случае р" должно делить все коэффициенты сг . иг(х) и р должно делить все коэффициенты иг(х). Таким образом, получается противоречие с посылкой примитивности иг(х). Точно так же рь делит сг только в том случае, если р" делит сь Следовательно, в силу единственности разложения сг — — асг, где а обратимо; поскольку О = асг щ(х) — сг иг(х) = сг (аи1(х) — иг(х)), получаем аиг(х) — иг(х) = О, 1 Таким образом, можно записать любой ненулевой полинам и(х) в виде и(х) = соп1(и) .
рр(и(х)), (3) где сонг(и) — содержание (сои генг) и, представляющее собой элемент 5, а рр (и(х) )— примитивиал часть (рггтг21ие раг$) и(х), являющаяся примитивным полиномом над Я. В случае, когда и(х) = О, удобно определить сонг(и) = рр(и(х)) = О. Комбинация лемм С и Н приводит к соотношениям сонг(и . е) = а сопС(и) сон!(е), рр(и(х) е(х)) = 6 рр(и(х)) рр(е(х)), (4) где а и Ь вЂ” обратимые элементы, зависящие от пути вычисления содержимого, причем а6 = 1.
При работе с полиномамн над целыми числами обратимыми элементами являются только +1 и — 1, и поэтому удобно определить рр(и(х)) так, чтобы ее старший коэффициент был положителен; тогда (4) истинно при а = Ь = 1. При работе с полиномами над полем можно принять сон!(и) = л(и), так что рр(и(х)) будет нормированным полиномом; в этом случае (4) вновь выполняется при а = Ь = 1 для всех и(х) и е(х). Например, пусть мы работаем с полиномами над целыми числами и пусть и(х) = — 26хе+ 39 и е(х) = 21х+ 14.
Тогда соп!(и) = -13, рр(и(х)) = 2х — 3, сопс(е) =+7, рр(е(х)) = Зх+ 2, сопс(и. е) = — 91, рр(и(х) е(х)) = бх +4х — 9х — 6. Наибольшие общие делители. В случае единственного разложения можно говорить о наибольшем общем делишеле двух элементов; это общий делитель, который делится на наибольшее количество простых элементов (см, формулу 4.5.2-(6)) .
Однако, поскольку область единственного разложения может иметь много обратимых элементов, в определении наибольшего общего делителя присутствует некоторая неоднозначность. Если ш — наибольший общий делитель и и е, то а ш, где а — обратимый элемент, тоже является наибольшим общим делителем. И обратно, предположение о единственности разложения на множители влечет за собой вывод о том, что если и шы и шз представляют собой наибольшие общие делители и и е, то ш| = а шз, где а — некоторый обратимый элемент, Другими словами, не имеет смысла говорить о конкретном наибольшем общем делителе (в оригинале— 'йо врез(г о! Ьйе йгеасез! сопппоп с)!е!зог".— Прим.
перев.) и и е. Существуег целое множество наибольших общих делителей, каждый из которых отличается от других на обратимый множитель. Рассмотрим теперь задачу поиска наибольшего общего делителя двух данных полиномов над алгебраической системой б, первоначально поставленну.ю Пабло Нуньесом (РаЫо Ь!пйех) в работе ТлЬго с(е А(яеЬга (Апсшегр, 1567). Если Я вЂ” поле, то проблема относительно проста; наш алгоритм деления, алгоритм В, может быть расширен до алгоритма вычисления наибольшего общего делителя так же, как алгоритм Евклида (алгоритм 4.5.2А), находящий наибольший общий делитель двух целых чисел, получается на основе алгоритма деления целых чисел: если е(х) = О, то йса(и(х),е(х)) = и(х); в противном случае йети(и(х),е(х)) = йсб(е(х),г(х)), где г(х) определяется (1).
Эта процедура называется алгоритмом Евклида для полиномов над полем. Впервые она была использована Симоном Стевином (Бппоп Бает!и) в 1 'Аг(сйшес!Оие (ВеЫеп, 1585); см. А. 6!гвЫ, 1,еа (Енегев Магйетабцнев !(е 5!топ В!ее!и 1 (1 еЫеп, 1634), 56. Например, необходимо найти Зсмк хе + хе + 10ха+ 10хз + 8хз + 2х+ 8 и Зхе + 5х + 9хэ + 4х+ 8, шод 13, используя алгоритм Евклида для полиномов нэд полем целых чисел по модулю 13.
Сначала запишем только коэффициенты для того, чтобы показать шаги алгоритма П. 907 3050948 1060 310 7 (5) 080 7 0 128 80 9 01124 011 0 304 Так что ха + х + 10хе + 10хз + 8х + 2х+ 8 равно (Ях~ + 7)(Зхв + 5хэ + Я~э + 4х + 8) + (11ха + 3~~ + 4). Аналогично Зх~ + 5ха + Яхт + 4х + 8 = (5х~ + 5)(11хя + Зх~ + 4) + (4х+ 1); 11ха+Зх~+4 = (бхэ+бх~+бх+5)(4х+1) + 12;. (6) 4х + 1 = (9х + 12) . 12 + О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
