Теорема о делении с остатком для многочленов

Теорема 8.1. Пусть F – поле, f (x), g (x) F [ x ], g (x) 0. Тогда существуют единственные многочлены q (x), r (x) F [ x ] такие, что f(x)=g (x) · q (x) +r (x), причем degr (x) < degg (x).

Доказательство. 1. Существование. Если f (x)=0 q (x)=0, r (x)=0, причем degr (x)=− < degg (x) 0. Если degf (x)< degg (x) q (x)=0, r (x)= f (x), причем degr (x)= degf (x)< deg g (x).

Пусть f (x) 0 и degf (x) degg (x). Пусть f (x) =a ₀ +a ₁ x+…+a_nxⁿ, g (x) =b ₀ +b ₁ x+…+b_mx^m n m. Доказательство проведем методом математической индукции по параметру n.

1) Пусть n =0 f (x) =a ₀ g (x) =b ₀ , причем deg r (x) = − < 0 =deg g (x).

2) Предположим, что утверждение верно для любого многочлена степени, меньшей n.

3) Докажем утверждение для многочлена степени n.

f (x) =a_o+…+a_nxⁿ

g (x) =b_o+…+b_mx^m ∙ b_m^{- 1} ∙ a_nx^n-m

h (x) =f (x) –g (x) ∙ b_m^{- 1} ∙ a_nx^n-m = a_o+…+ (a_nxⁿ–b_mb_m^{- 1} a_nx^mx^n-m) h (x) – многочлен степени, меньшей n q ₁(x), r ₁(x) F [ x ]: h (x) =g (x) ∙ q ₁(x) +r ₁(x), где deg r ₁(x) < deg g (x)

f (x)– g (x) =g (x) ∙ q ₁(x) +r ₁(x) , причем deg r (x) < deg g (x).

Из 1)–3) по методу математической индукции следует, что утверждение верно .

2. Единственность. Пусть f (x) =g (x) ∙ q ₁(x) +r ₁(x) (1) и f (x) =g (x) ∙ q ₂(x) +r ₂(x) (2). Покажем, что q ₁ =q ₂, r ₁ =r ₂. Вычтем из равенства (1) равенство (2): 0= g (x)(q ₁– q ₂) + (r ₁– r ₂) r ₂– r ₁ =g (x)(q ₁– q ₂) (3).

Допустим, что q ₁– q ₂ 0. Согласно теореме 3, F [ x ]–область целостности. Поэтому в F [ x ]нет делителей нуля и из (3) следует, что . Тогда, с одной стороны, deg (r ₂– r ₁) , т.е. .

С другой стороны, , т.е. deg (r ₂ -r ₁) < deg g. Противоречие. Следовательно, . Теорема доказана.

9. Алгоритм Евклида. НОД и НОК многочленов.

Линейное представление НОД.

Определение 9.1. Пусть F – поле, f (x), g (x) F [ x ]. Многочлен d (x) F [ x ] называется наибольшим общим делителем многочленов f (x)и g (x) (или коротко, НОД f (x)и g (x)) и обозначается d (x)=(f (x), g (x)), если выполняются два условия:

1) d (x) – общий делитель многочленов f (x)и g (x), т.е. и ;

2) d(x) делится на любой общий делитель многочленов f(x) и g(x), т.е. если и , то .

Определение 9.2. Пусть K – ассоциативно-коммутативное кольцо с единицей. Элементы a и b кольца K называются ассоциированными в K и обозначаются a ∼ b, если и .

Лемма 9.1. Пусть F – поле, f (x), g (x), q (x), r (x) F [ x ], g≠ 0, и f=g·q+r (1). Тогда НОД многочленов f и g и НОД многочленов g и r ассоциированы, т.е. (f, g)∼ (g, r).

Доказательство. Пусть d ₁=(f, g), d ₂=(g, r). Так как и , то из (1) имеем (2). Так как и , то из (1) имеем (3). Из (2) и (3) следует, что d ₁∼ d ₂. Лемма доказана.

Лемма 9.2. НОД двух многочленов определяется однозначно с точностью до ассоциированности.

Пусть F – поле, f (x), g (x) F [ x ], g≠ 0. Для нахождения НОД многочленов f и g применяется алгоритм Евклида: применяем теорему о делении с остатком к f и g; если r≠ 0, то применяем теорему о делении с остатком к g и r, и т.д.:

(4)

...

...

Последовательность равенств (4) представляет алгоритм Евклида.

Покажем, что процесс деления в алгоритме Евклида является конечным. Рассмотрим последовательность (5). Так как (5) – убывающая последовательность целых неотрицательных чисел, она является конечной и содержит число членов . Следовательно, процесс деления с остатком в алгоритме Евклида (4) конечен.

Пусть – последний отличный от нуля остаток. Покажем, что (f, g)∼ . Действительно, по лемме 9.1 (f, g)∼ (g, )∼ ( , )∼ …∼ ( , )∼ .

Замечание 9.1. Так как по лемме 9.2 НОД двух многочленов определяется однозначно с точностью до ассоциированности, то будем писать (f, g) = , т.е. НОД многочленов f и g равен последнему отличному от нуля остатку в алгоритме Евклида (4).

Определение 9.3. Пусть F – поле, f (x), g (x) F [ x ]. Многочлен m (x) F [ x ] называется наименьшим общим кратным многочленов f (x)и g (x) (или коротко, НОК f (x)и g (x)) и обозначается m (x)=[ f (x), g (x)], если выполняются два условия:

1) m (x) – общее кратное многочленов f (x)и g (x), т.е. и ;

2) m (x) делит любое общее кратное многочленов f (x)и g (x), т.е. если и , то .

Лемма 9.3. НОК двух многочленов определяется однозначно с точностью до ассоциированности.

Лемма 9.3. Пусть F – поле, f (x), g (x) F [ x ]. Тогда [ f, g ]= .

Теорема 9.1 (теорема о линейном представлении НОД). Пусть F – поле, f (x), g (x) F [ x ], g≠ 0, d= (f, g). Тогда (6).

Доказательство. Рассмотрим алгоритм Евклида (4). Выражая из последнего равенства (4) и заменяя их значениями из предыдущих равенств (4), через конечное число шагов получим , где . Теорема доказана.

Равенство (6) называется линейным представлением НОД многочленов f(x) и g(x).

10. Деление многочлена на (х-с). Схема Горнера.

Пусть F – поле, f (x) =a ₀ xⁿ+a ₁ x^{n- 1} +a_{n- 1} x+a_n ∈ F [ x ] – многочлен, записанный по убывающим степеням. Пусть с ∈ F. Разделим f (x) на (х–с). По теореме Безу существует q (x)∈ F [ x ]: f (x) = (x – c) ·q (x) +f (c)(1), где f (c) =r. Пусть q (x) =b ₀ x^{n- 1} +b ₁ x^{n- 2} +…+b_{n- 2} x+b_{n- 1}. Подставим в (1) выражения для f и q:

(2) a ₀ xⁿ+a ₁ x^{n - 1} +…+a_{n -1} x+a_n= (x – c)·(b ₀ x^{n - 1} +b ₁ x^{n - 2} +…+b_{n -2} x+b_{n - 1}) +r.

Приравняем коэффициенты при соответствующих степенях переменной:

a ₀ =b ₀ b ₀ =a ₀

a ₁ =b ₁– b ₀ c b ₁ =a ₀ c+a ₁

a ₂ =b ₂– b ₁ c b ₂ =b ₁ c+a ₂

(3) ……….. (4) ………..

a_{n – 1} =b_{n –1}– b_{n – 2} c b_{n - 1} =b_{n - 2} c+a_{n - 2}

a_n=r – b_{n – 1} c r =b_{n - 1} c+a_n

Система (4) позволяет разделить многочлен f (x) на (х – с), т.е. получить коэффициенты частного и остаток. Систему (4) удобно записывать в виде схемы, которая называется схемой Горнера.

коэффициенты f (x)

коэффициенты q (x) r=f (c)

11. Разложение многочлена по степеням (х – с)

Пусть F – поле, f(x) = a ₀ xⁿ+a ₁ x^{n- 1} +…+a_{n- 1} x+a_n ∈ F [ x ], c ∈ F. Найдем разложение многочлена f(x) по степеням (x – с), т.е. найдем представление f(x) в виде

f(x)=d ₀ (x – c)ⁿ+d ₁ (x – c)^{n- 1} + d ₂ (x – c)^{n- 2} +…+ d_{n- 1} (x – c)+d_n .

Разделим f(x) на (x – c), при этом получим искомое частное q ₁ и остаток r ₀. Далее, разделим частное q ₁ на r ₁, и т.д.:

f(x) = (x – c)·q ₁ (x)+r ₀, deg q ₁ (x) = n –1

q ₁ (x) = (x – c)·q ₂ (x)+r ₁, deg q ₂ (x) = n –2

(1) ….

q_{n- 2} (x)=(x – c)·q_{n- 1} (x)+r_{n- 2}, deg q_{n- 1} (x)= n – (n –1 )= 1

q_{n- 1} (x)=(x – c)·q_n(x)+r ₁, (где q_n(x)=a ₀ ), deg q_n(x)= n–n= 0

Из (1) следует, что f(x) = (x – c)q ₁ +r ₀ =(x – c)·((x – c)·q ₁ +r ₁ ))+r ₀= (x – c) ² q ₂ +(x – c)r ₁ +r ₀ =

= (x – c) ² ((x – c)·q ₃ +r ₂ )+(x – c)·r ₁ +r ₀ =(x – c) ³ q ₃ +(x – c) ² r ₂ +(x-c)·r ₁ +r ₀ =…=

= (x – c)^{n- 1} q_{n- 1} +(x – c)^{n- 2} r_{n- 2} +…+(x – c) ² r ₂ +(x – c)r ₁ +r ₀ =(x – c)ⁿa ₀ +(x – c)^{n- 1} r_{n- 1} +…+(x – c) ² r ₂ +(x – c)·r ₁ +r ₀.

Таким образом, f(x)=a ₀ (x – c)ⁿ+r_{n- 1} (x – c)^{n- 1} +…+r ₂ (x – c) ² +r ₁ (x – c)+r ₀ (2) - разложение f(x) по степеням (x – c). Формулу (2) удобно получать с помощью схемы Горнера.