Кольцо многочленов. Определение кольца многочленов. Деление с остатком и его свойства. Разложение на неприводимые множители (Избранные лекции), страница 2

+ pn qm .ÔÍ-12ÌÃÒÓp = p0 + p1 + . . . pk ,ÌÃÒÓÔÍ-12J Любой многочлен p ∈ K[x1 , . . . , xn ] степени k можно представить в видеÔÍ-12ÔÍ-12Следствие 17.1. Если K — целостное кольцо, то при перемножении многочленов их степени складываются.ÌÃÒÓÔÍ-12степени k + 1. Несложно убедиться в том, что многочлен pe(x) = p(x) −ÌÃÒÓ46ak+1 k+1−mxq(x) имеетbme Ностепень не выше k. Поэтому для него имеет место представление (17.1), т.е. pe = αeq + β.тогдаaak+1 k+1−mk+1 k+1−mexq(x) =x+αe(x) q(x) + β(x),p(x) = pe(x) +bmbmт.е. имеет место представление (17.1).Согласно методу математической индукции, любой многочлен p может быть разложен помногочлену q в виде (17.1). Существование представления (17.1) доказано.Пустьp = αq + β = α1 q + β1 .ТогдаÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-12ÔÍ-12ÌÃÒÓÔÍ-1217.

КОЛЬЦО МНОГОЧЛЕНОВÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓÌÃÒÓВторое свойство означает, что рассматриваемое отношение транзитивно. Очевидно, что онои рефлексивно, но не является симметричным или антисимметричным. Можно утверждать, чтоесли p ... q, q ... p, то эти многочлены имеют одинаковую степень и один получается из другогоумножением на элемент поля P (многочлен нулевой степени).

Если ограничиться многочленами,у которых старший коэффициент равен 1, называемыми унитарными многочленами, тоотношение делимости становится антисимметричным, а значит, отношением порядка. Далееговоря о делителях многочленов, мы будем иметь в виду унитарные многочлены.Среди всех делителей данных многочленов p и q существуют общие делители. Ясно чтостепень таких делителей не превышает минимальной из степеней p и q. Среди всех общихделителей p и q существует многочлен наивысшей степени. Как следует из дальнейшего изложения, такой многочлен единственный (в классе унитарных многочленов). Он называетсянаибольшим общим делителем (НОД) многочленов p и q. Мы обозначим его НОД(p, q).Для вычисления НОД двух многочленов можно использовать алгоритм Евклида, состоящий в следующим.

Делим многочлен p на многочлен q с остатком, получая частное α0 иостаток β0 . Затем делим q на α0 с остатком, получая частное α1 и остаток β1 . Этот процесспоследовательного деления в какой-то момент прервется, поскольку на каждом шаге очереднойостаток будет иметь степень, меньшую чем предыдущий по крайней мере на единицу. ПолучимÔÍ-12В представлении (17.1) многочлен α называется частным, а многочлен остатком отделения многочлена p на многочлен q. Фактически это представление позволяет ввести двеоперации в кольце многочленов: p : q = α и p mod q = β.

Первая операция — вычислениечастного при делении многочленов, вторая — вычисление остатка.Если в представлении (17.1) β = 0, то говорят, что многочлен p делится на многочленq и пишут p ... q, при этом многочлен q называют делителем многочлена p, а многочлен p —кратным многочлена q.На множестве P [x] всех многочленов возникает отношение делимости.

Непосредственно изопределения вытекают простейшие свойства этого отношения:1) p ... q ⇒ deg p > deg q;2) p ... q, q ... r ⇒ p ... r;3) p1 ... q, p2 ... q ⇒ p1 ± p2 ... q;4) p ... q ⇔ pr ... qr.ÌÃÒÓÔÍ-12Однако многочлен слева имеет степень не менее deg q, в то время как правая часть имеет степеньменьше deg q.

Такое равенство возможно только в случае, когда и слева, и справа стоят нулевыемногочлены. В этом случае α = α1 , β = β1 , т.е. два различных представления совпадают. IÔÍ-12ÔÍ-12(α − α1 )q = β1 − β.ÌÃÒÓÔÍ-12ÌÃÒÓ47ÔÍ-12(17.2)ÔÍ-12Из первого соотношения этой системы можно сделать вывод, что пары многочленов p иq, q и β0 имеют одно и то же множество общих делителей.

В самом деле, если r — общийделитель p и q, то в силу равенства β0 = p − α0 q многочлен r является делителем β0 , а значит,общим делителем пары q и β0 . Если же r — общий делитель пары q и β0 , то в силу равенстваp = α0 q + β0 , он является делителем p а потому общим делителем пары p и q.Используя второе, третье и т.д. соотношения системы, заключаем, что все пары многочленов p и q, q и β0 , β0 и β1 , . . . , βk−1 и βk имеют одно и то же множество общих делителей. Но изпоследнего соотношения системы вытекает, что множество общих делителей пары βk−1 и βk —это множество всех делителей многочлена βk , причем сам многочлен βk есть общий делительлюбой из указанных выше пар наивысшей степени, т.е.

βk = НОД(p, q).Изложенный алгоритм вычисления НОД позволяет сделать два дополнительных вывода.Во-первых, любой общий делитель пары многочленов p и q является делителем НОД этих многочленов. Во-вторых, верно следующее утверждение.p = α0 q + β0 ,q = α1 β0 + β1 ,β0 = α2 β1 + β2 ,. . . . . . . . . .βk−2 = αk βk−1 + βk ,βk−1 = αk+1 βk .ÌÃÒÓсистему соотношенийÔÍ-12ÔÍ-12ÌÃÒÓÌÃÒÓÌÃÒÓÔÍ-1217. КОЛЬЦО МНОГОЧЛЕНОВµp + νq = d.J Запишем для многочленов p и q последовательность делений (17.2).

Тогда βk = НОД(p, q) = d.Из предпоследнего равенства (17.2) заключаем, чтоd = µk−1 βk−3 + νk−1 βk−2 ,где µk−1 = νk , νk−1 = µk − νk αk−1 . Продолжая процесс последовательного исключения старшегоостатка, придем к утверждению теоремы. IJ Свойство 5 вытекает из следующих соображений. Пусть d = НОД(p, q), d0 = НОД(pr, qr).Очевидно, что pr ... dr, qr ... dr, т.е. dr — общий делитель пары pr и qr, а потому являетсяделителем d0 . В силу теоремы 17.3 имеем представление d = µp + νq, откуда dr = µ(pr) + ν(qr).Следовательно, любой общий делитель пары pr и qr является делителем многочлена dr.

ВÔÍ-12На основании этих следствий из алгоритма Евклида можно получить дальнейшие свойстваотношения делимости:5) НОД(pr, qr) = r НОД(p, q);НОД(p, q)p q=;6) если r — общий делитель p и q, то НОД ,r rr7) если pr ... q, НОД(r, q) = 1, то p ... q;8) если НОД(r, q) = 1, то НОД(pr, q) = НОД(p, q);9) если p ...

q, p ... r, НОД(q, r) = 1, то p ... qr.ÌÃÒÓÔÍ-12ÌÃÒÓÔÍ-12ÌÃÒÓгде µk = 1, νk = −αk .Второе с конца равенство в системе (17.2) имеет вид βk−3 = αk−1 βk−2 + βk−1 . Отсюда получаем βk−1 = βk−3 − αk−1 βk−2 . С помощью этого представления исключим βk−1 из равенства(17.3): d = νk βk−3 + (µk − νk αk−1 )βk−2 . Следовательно,ÌÃÒÓÔÍ-12(17.3)ÔÍ-12ÔÍ-12d = µk βk−2 + νk βk−1 ,ÌÃÒÓÌÃÒÓТеорема 17.3. Если d = НОД(p, q), то существуют такие многочлены µ и ν, чтоÌÃÒÓÔÍ-12ÌÃÒÓ48частности, dr ...

d0 . Таким образом, многочлены d0 и dr делятся один на другой. С учетом ихунитарности заключаем, что d0 = dr.Свойство 6 — переформулировкапредыдущего. Действительно, положим p0 = p/r, q 0 = q/r.ÔÍ-12p = µpr + νqr.ÌÃÒÓТеорема 17.4. Для любых многочленов p, q, r верно равенствоНОД(p, q, r) = НОД НОД(p, q), r = НОД p, НОД(q, r) .Любая пара многочленов p и q имеет общие кратные (например pq). Среди всех общихкратных пары p и q существует многочлен наименьшей степени. Он (среди унитарных) единственный. Его называют Наименьшим общим кратным (НОК) и обозначают НОК(p, q).Вычисление наименьшего общего кратного двух многочленов сводится к вычислению их наибольшего общего делителя согласно следующей теореме.J Обозначим d = НОД(p, q), p0 = p/d, q 0 = q/d.

Тогдаpqявляется общим кратным пары многочленов p = p0 d и q = q 0 d.dÌÃÒÓÔÍ-12многочлен s =pqp0 q 0 d 2== p0 q 0 d, и мы видим, чтоddÔÍ-12Теорема 17.5. Для любых двух многочленов p и q верно равенствоpqНОК(p, q) =.НОД(p, q)ÌÃÒÓJ Очевидно, что наибольший общий делитель как функция от трех многочленов не зависит отпорядка аргументов.

Поэтому в теореме можно ограничиться доказательством только первогоравенства. Это равенство будет доказано, если мы установим что тройка многочленов p, q, r ипара многочленов НОД(p, q) и r имеют одно и то же множество общих делителей.Если d — общий делитель многочленов p, q, r, то он делится на НОД(p, q), а следовательно,является общим делителем пары многочленов НОД(p, q) и r. Пусть d — общий делитель парыНОД(p, q) и r.

Тогда d — делитель НОД(p, q), а потому является общим делителем многочленовp и q. Значит, он — общий делитель многочленов p, q, r. IÔÍ-12ÌÃÒÓПонятие наибольшего общего делителя двух многочленов без проблем переносится на любоечисло многочленов.

Остановимся на случае трех многочленов. Тройка многочленов p, q, r имеетобщие делители (например, 1), причем степень общего делителя не превышает минимальной изстепеней трех многочленов. Следовательно, среди общих делителей существует многочлен наивысшей степени. Такой многочлен называется наибольшим общим делителем трех многочленов. Оказывается, вычисление НОД трех (и более) многочленов сводится к последовательномувычислению НОД пар многочленов. Это вытекает из следующей теоремы.ÌÃÒÓÔÍ-12В правой части равенства оба слагаемых делятся на q.

Значит, и многочлен p делится на q.Чтобы доказать свойство 8, отметим, что любой общий делитель пары p и q является такжеобщим делителем пары pr и q. Пусть s — общий делитель многочленов pr и q. Обозначимd = НОД(r, s). Так как q ... s, то d — общий делитель многочленов r и q, а так как НОД(r, q) = 1,то d = 1. Итак, имеем: НОД(r, s) = 1, pr ... s. Отсюда следует, что p ... s и s является общимделителем пары p и q.

Мы доказали, что пары p и q, pr и q имеют одно и то же множестводелителей. Значит, эти пары имеют один и тот же НОД.Для доказательства свойства 9 положим p/q = s (это можно в силу отношения p ... q). Тогдаусловие p ... r можно записать в виде qs ... r. Отсюда в силу свойства 7 с учетом условияНОД(q, r) = 1 заключаем, что s ...