Лекции по алгебре - Фаддеев Д.К.
Скачать (прямая ссылка):
5. Схема Хорнера и теорема Безу. Если для полиномов f(x) и g(x) из А[х] существует такой полином п(х)^ А[х], что f(x) = = g(x)rt(x), то говорят, что полином 1(х) делится на полином g(x). Наша ближайшая задача заключается в выяснении вопроса о делимости f(x)^A[x] на линейный двучлен х — с при с є А.
Прежде всего установим, что всегда осуществимо так называемое деление с остатком: f(x) = (x — c)h(x)+r при ге А. Здесь полином п(х) называется неполным частным, а г — остатком.
Теорема 3. Пусть f(x)=aoxn-\-aixn-l-\- ... + о„ є Л [х] и сєА Найдутся полином п(х)^ А[х] и элемент г є А такие, что f(x) = (x-c)h(x) + r.
Доказательство. Естественно искать h(x) в форме box"-1 + Ь\Хп~2 + ... + Ьп-\. Сравнение коэффициентов показывает равносильность равенства а0хп + Oix"-1 + ... + ап = = (х — с) (box"-1 + Ъ\хп-'1 + ... + bn-i) + г цепочке равенств
58
ПРОСТЕЙШИЕ СВЕДЕНИЯ ОБ АЛГЕБРЕ ПОЛИНОМОВ
[ГЛ. III
откуда последовательно определяются коэффициенты п(х) и остаток г:
O0 = O0,
O1=Ci1 + cbQ. Ь2 = а2 + сЬь
bn-\ = an_x + cbn_2, r = an + cbn_x.
Теорема доказана. Кроме того, получен очень удобный способ вычисления коэффициентов п(х) и остатка г. Этот способ носит название схемы Хорнера.
Заметим сразу, что остаток г равен значению f(c) полинома f(x) при х = с. Действительно, переходя в равенстве f(x) = = {х— с)п(х) + г к значениям при х = с, получим f(c) = = (с — c)h(c) + r, откуда r = f(c).
Пример. Найти неполное частное и остаток при делении полинома X5 на X — 2.
Выпишем последовательно коэффициенты полинома х5 и, после вертикальной черты, число 2:
1 0 0 0 0 012.
Под этой строкой запишем коэффициенты неполного частного и остаток, пользуясь только что выведенными формулами:
1 0 0 0 0 012
1 2 4 8 16 32
(остаток — подчеркнутое число). Итак,
х5 = (х — 2)(х* + 2х3 + 4х2 + 8х + 16) + 32.
Теорема 4 (Безу). Для того чтобы полином f(x)^A[x] делился на х — с, необходимо и достаточно, чтобы f(c) = 0.
Доказательство. Необходимость. Пусть f(x) делится на X — с, т. е. f(x) = (x — c)h(x). Тогда /(с) = 0.
Достаточность. Пусть f(c) = 0. Тогда в равенстве f(x) = = (х — c)h(x) + г будет г = f(с) = 0, т. е. f(x) = (x — c)h(х). Теорема доказана полностью.
Элемент с кольца А называется корнем полинома f(x), если f(c) = 0. Таким образом, теорема Безу может быть сформулирована так: для того чтобы полином f(x)<^A[x] делился на двучлен X — с при с = А, необходимо и достаточно, чтобы с было корнем fix).
6. Число корней полинома в коммутативной области целостности.
Лемма. В области целостности возможно сокращение в равенстве, т. е. ab = ас при афО следует b = с.
ПОЛИНОМЫ OT ОДНОЙ БУКВЫ
59
Действительно, равенство ab = ас равносильно равенству а{Ь — с) = 0. Так как а Ф0 и мы оперируем в области целостности, должно быть Ъ — с = 0, т. е. b = с.
Теорема 5. Пусть f(х) = а0хп + аххп~1 -f- ... -f- ап — полином из А[х], где А — (коммутативная) область целостности. Тогда число корней f(x) в А не превосходит его степени п.
Доказательство. Применим метод математической индукции по степени полинома. База для индукции имеется — полином ао Ф 0 нулевой степени не имеет корней. Допустим, что п ^ 1 и что теорема доказана для полиномов степени п—1, и в этом предположении докажем ее для полинома f(x) степени я. Если f(x) не имеет корней в А, то утверждение теоремы верно. Пусть корни есть и Ci — один из корней. Тогда
f(x) = (x— ci)h(x), где h(x) — U0X"-1 + b\xn~2 -f- ...
... +&„_! є= А [х],
Если C2 — какой-либо корень f(x), отличный от сь то 0 = = /(с2) = (с2— Ci)«(c2), но C2 — Ci=T^O, следовательно, я(с2) = 0. Таким образом, любой корень /(х), кроме си является корнем полинома h(x) степени п—1. В силу индуктивного предположения этот полином имеет не более п—1 корней в А и, следовательно, f(x) имеет не более л корней, что и требовалось доказать.
Заметим, что предположение о том, что кольцо А есть область целостности, здесь существенно. Так, в кольце вычетов по модулю 8 полином X2— 1 имеет 4 корня: 1, 3, 5, 7.
7. Теорема о тождестве. Пусть, по-прежнему, А — коммутативная область целостности и А[х] — кольцо полиномов над А.
Теорема 6 (о тождестве). Если А содержит бесконечно много элементов, то два полинома fx(x) и f2(x), принимающие одинаковые значения при всех с є А, равны.
Доказательство. Допустим, что разность F(x) = /і(л-) — — f2(x) отлична от нуля, так что F(x) = а0хп + aix"-1 -4- ... -f- ап при аоФ0. Возьмем попарно различные элементы си C2,..., сп+\ кольца А. Тогда, в силу условия теоремы, /[(Ci) = Z2(C1), Zi(C2) = = /2(?), /і(с«+і) = /2(с„+і), так что полином п-й степени F(x) имеет более чем л корней: сь с2, сп+и Это невозможно. Следовательно, F(x) = 0 и Z1 (х) = /2 (х), что и требовалось доказать.
Здесь было существенно, что кольцо А имеет бесконечно много элементов. Так, если A = QF(S) есть поле вычетов по модулю 5 и -Мх) = х5 + х4 + 2х2 + х+ 1, f2(x) = x* + 2x2 + 2x+ 1 -полиномы из А\х], то /,(O)=Z2(O)= 1, Z1(I) = Z2(I)=I, Z1 (2) = J= Z2 (2) = 4, Zi(3) = Z2(3)= 1, Zi (4) = Z2 (4) =2. Полиномы Z1W и h(x) принимают одинаковые значения при всех элементах кольца 'А, и тем не менее они различны. Их разность х5 — х есть отличный от нуля полином, все значения которого в А равны 0.