Составители:
Рубрика:
Многочлены q
l,m
удобно изобразить в виде дерева.
Окончательная цель – вычислить остатки от деления многочле-
на P (x) на биномы q
l,0
= x − c
l
. Для этого вычислить остатки от
деления P (x) на q
l,m
(x) для каждого q
l,m
, начиная с m = k и кон-
чая m = 0. При m = k приходится делить многочлен P (x) степени
n−1 на многочлен q
0,k
(x) степени n (см. формулы (7.2) и (8.5) соот-
ветственно). Очевидно, остатком такого деления явится многочлен
r
0,k
= P (x). Далее через r
l,m
(x) обозначим остаток от деления мно-
гочлена P (x) на многочлен q
l,m
(x) (степени 2
m
). Очевидно, степень
многочлена r
l,m
не превосходит 2
m
− 1.
Перепишем представления (8.7) в краткой форме
q
l,m
(x) = q
0
(x) ·q
00
(x), (8.8)
где
q
0
(x) = q
l,m−1
(x), (8.9)
q
00
(x) = q
l+2
m−1
,m−1
(x). (8.10)
Лемма 2. Остаток от деления P (x) на q
0
(x) равен остатку
от деления r
l,m
(x) на q
0
(x), а остаток от деления P (x) на q
00
(x)
равен остатку от деления r
l,m
(x) на q
00
(x).
Д о к а з а т е л ь с т в о. Очевидно (см. формулу (8.9)), что
p(x) = h
0
(x)q
0
(x) + r
l,m−1
(x), (8.11)
p(x) =
˜
h(x)q
l,m
(x) + r
l,m
(x), (8.12)
откуда h
0
(x)q
0
(x) + r
l,m−1
(x) =
˜
h(x)q
l,m
(x) + r
l,m
(x).
Ввиду представления (8.8) q
l,m
(x) делится на q
0
(x), а значит
r
l,m−1
(x) совпадает с остатком от деления r
l,m
(x) на q
0
(x). Первая
часть леммы доказана.
Аналогичным образом доказывается вторая её часть; при этом
вместо соотношения (8.11) используем соотношение
p(x) = h
00
(x)q
00
(x) + r
l+2
m−1
,m−1
(x). (8.13)
Лемма доказана.
Следствие. Остатки от деления P (x) на q
0
(x) и на q
00
(x)
можно получить делением на q
0
и q
00
многочлена r
l,m
степени
2
m
−1, а не исходного многочлена степени 2
k
−1. Можно ввести
18
Страницы
- « первая
- ‹ предыдущая
- …
- 15
- 16
- 17
- 18
- 19
- …
- следующая ›
- последняя »
