Элементы алгебры: комплексные числа, системы линейных уравнений, многочлены. Ильин С.Н. - 59 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

Шаг k: Поделим r
k−1
с остатком на r
k
. Получим
r
k−1
= q
k
r
k
+ r
k+1
, deg r
k+1
< deg r
k
.
Если r
k+1
= 0, то алгоритм завершен и НОД (a, b) = r
k
, в противном
случае переходим к шагу k + 1.
Обоснование алгоритма. Поскольку последовательность степеней остат-
ков r
0
, r
1
,. . . является строго убывающей, через некоторое число m
шагов (m ≤ deg r
0
+ 1) получим deg r
m+1
= −∞, то есть, r
m+1
= 0
и алгоритм закончит свою работу. Покажем, что r
m
= НОД (a, b).
Имеем систему равенств:
a = q
0
b + r
1
,
b = q
1
r
1
+ r
2
,
. . . . . .
r
m−2
= q
m−1
r
m−1
+ r
m
,
r
m−1
= q
m
r
m
.
(6.1)
Очевидно, r
m
| r
m
. Согласно последнему равенству системы (6.1)
r
m
| r
m−1
. Тогда из предпоследнего равенства вытекает r
m
| r
m−2
.
Воспользовавшись третьим с конца равенством, выводим r
m
| r
m−3
и так
далее. В итоге, получаем r
m
| b и r
m
| a, тем самым, для r
m
выполено
условие 1) определения НОД.
Пусть теперь c | a и c | b. Двигаясь по системе (6.1) сверху вниз,
последовательно получаем c | r
1
, c | r
2
,. . . , c | r
m
, то есть, верно и условие
2). Следовательно, r
m
= НОД (a, b).C
Перепишем равенства системы (6.1) (кроме последнего) в виде
a − q
0
b = r
1
,
b − q
1
r
1
= r
2
,
. . . . . .
r
m−2
− q
m−1
r
m−1
= r
m
.
(6.2)
Двигаясь по системе (6.2) сверху вниз, замечаем, что r
1
выражается через
многочлены a и b, многочлен r
2
выражается через b, r
1
и поэтому опять
выражается через a и b, и так далее. В итоге, получим выражение
многочлена r
m
через a и b. Таким образом, опираясь дополнительно
на предложение 6.3 и алгоритм Евклида, получаем доказательство
следующей теоремы.
57
      Шаг k : Поделим rk−1 с остатком на rk . Получим

                   rk−1 = qk rk + rk+1 ,        deg rk+1 < deg rk .

Если rk+1 = 0, то алгоритм завершен и НОД (a, b) = rk , в противном
случае переходим к шагу k + 1.
Обоснование алгоритма. Поскольку последовательность степеней остат-
ков r0 , r1 ,. . . является строго убывающей, через некоторое число m
шагов (m ≤ deg r0 + 1) получим deg rm+1 = −∞, то есть, rm+1 = 0
и алгоритм закончит свою работу. Покажем, что rm = НОД (a, b).
     Имеем систему равенств:

                              a = q 0 b + r1 ,
                              b = q1 r1 + r2 ,
                            ...   ...                                        (6.1)
                           rm−2 = qm−1 rm−1 + rm ,
                           rm−1 = qm rm .

Очевидно, rm | rm . Согласно последнему равенству системы (6.1)
rm | rm−1 . Тогда из предпоследнего равенства вытекает rm | rm−2 .
Воспользовавшись третьим с конца равенством, выводим rm | rm−3 и так
далее. В итоге, получаем rm | b и rm | a, тем самым, для rm выполено
условие 1) определения НОД.
      Пусть теперь c | a и c | b. Двигаясь по системе (6.1) сверху вниз,
последовательно получаем c | r1 , c | r2 ,. . . , c | rm , то есть, верно и условие
2). Следовательно, rm = НОД (a, b).C
      Перепишем равенства системы (6.1) (кроме последнего) в виде

                                    a − q 0 b = r1 ,
                                   b − q 1 r1 = r2 ,
                                                                             (6.2)
                                        ...     ...
                           rm−2 − qm−1 rm−1 = rm .

Двигаясь по системе (6.2) сверху вниз, замечаем, что r1 выражается через
многочлены a и b, многочлен r2 выражается через b, r1 и поэтому опять
выражается через a и b, и так далее. В итоге, получим выражение
многочлена rm через a и b. Таким образом, опираясь дополнительно
на предложение 6.3 и алгоритм Евклида, получаем доказательство
следующей теоремы.

                                           57

Страницы