Алгоритм Евклида

Пусть даны многочлены f(x) и g(x). Делим f(x) на g(x) и получаем остаток . Делим затем g(x) на и получаем остаток . Делим на и т.д. Т.к. степени остатков все время понижаются, то в этой цепочке последовательных делений мы должны дойти до такого места, на котором деление совершится нацело и процесс остановится. Тот остаток на который нацело делится предыдущий остаток , и будет НОД многочленов f(x) и g(x).

Последнее равенство показывает, что служит делителем . Отсюда следует, что оба слагаемых левой и правой части делятся на , поэтому будет делителем и для . Далее аналогично будет делителем и для ,…, , . Отсюда, ввиду второго равенства следует что есть делитель для g(x), и из первого равенства и для f(x). Таким образом, является делителем и для f(x) и для g(x).

Возьмем произвольный общий делитель многочленов f(x) и g(x). Так как левая часть и первое слагаемое правой части первого из равенств делятся на , то так же будет делиться на . Переходя ко второму и след. равенствам так же получим что на делятся многочлены , … Если будет доказано что и делятся на то из предпоследнего неравенства получим, что делится на . Таким образом на самом деле будет НОД для f(x) и g(x).

То для всякого можно подобрать такое , что

Действительно, пусть , число уже дано. Покажем, что если за число взять , то оно будет удовл. требуемым условиям. В самом деле,

т.е.

Так как и , то и поэтому , что и требовалось доказать.

Выведем след. формулу: Пусть дан многочлен с любыми комплексными коэффициентами. Заменим x на (x+h), где h - второе неизвестное. Разлагая в правой части каждую из степеней , , по биному и собирая все члены с одинаковыми степенями h, получим равенство: ,докажем формулу Тейлора дающую разложение f(x+h) по степеням приращения h. Непрерывность произвольного многочлена f(x) в любой точке доказывается след. образом: где

Многочлен есть многочлен без свободного члена, поэтому по лемме 1 можно подобрать такое что при будет , то есть , что и требовалось доказать.

Поиск по сайту: