Методические указания к лабораторным работам по курсу "Дискретная математика". Домашова Д.В - 7 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

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

Рубрика: 

Если общих делителей многочленов нулевой степени f(x) и g(x) не име-
ют, то они называются взаимно простыми.
Определение. Наибольшим Общим Делителем отличных от нуля много-
членов f(x) и g(x) называется такой многочлен d(x), который является их общим
делителем и, вместе с тем, сам делится на любой другой общий делитель этих
многочленов.
Обозначение: НОД (f(x),g(x))
Вопрос: Существует ли НОД ?
Да, способ отыскания – метод последовательного деления
2.5 Алгоритм Евклида
Даны: f(x), g(x).
Найти НОД.
Делим f(x) на g(x), получаем r
1
(x) делим g(x) на r
1
(x), получаем r
2
(x), r
1
(x)
на r
2
(x) –> r
3
(x) степени остатков все время понижаются => дойдем до такого
места, на котором деление совершается нацело => процесс остановиться.
Тот остаток r
к
(x), на который нацело делится предыдущий остаток r
к-1
(x)
и будет НОД f(x) и g(x).
f(x)=g(x)g
1
(x)+r
1
(x)
g(x)=r
1
(x)q
2
(x)+r
2
(x)
r
1
(x) =r
2
(x)q
3
(x)+r
3
(x)
…
r
k-3
(x) =r
k-2
(x)q
k-1
(x)+r
k-1
(x)
r
k-2
(x) =r
k-1
(x)q
k
(x)+r
k
(x)
r
k-1
(x) =r
k
(x)q
k+1
(x) => r
k
(x) НОД
Если d(x) – НОД f(x) и g(x) => cd(x), c
≠0 – НОД (f(x), g(x));
Можно условиться, что старший коэффициент НОД - а будем считать
равным единице.
Утверждение. Два многочлена взаимно просты
если их НОД=1
Теорема. Если d(x)=НОД(f(x),g(x)) => можно найти такие многочлены
u(x) и v(x) : f(x)u(x)+g(x)v(x)=d(x). Можно при этом считать степени многочле-
нов f(x) и g(x) больше 0, что степень u(x) меньше степени g(x), а степень v(x)
меньше степени f(x).
Доказательство основано на алгоритме Евклида. Если мы учтем, что
r
k
(x)=d(x) и положим u
1
(x)=1, v
1
(x)=-q
k
(x) то из предпоследнего равенства сле-
дует:
d(x)=r
k-3
(x)u
2
(x)+ r
k-2
(x)v
2
(x), где u
2
(x)=v
1
(x), v
2
(x)=u
1
(x)-v
1
(x)q
k-1
(x)
Продолжая подниматься по равенствам вверх, мы придем к доказывае-
мому.
Пусть u(x) и v(x) уже найдены, но предположим что deg(u(x))
≥deg(g(x))
делим u(x) на g(x): u(x)=g(x)q(x)+r(x), где deg(r(x))<deg(g(x))
Подставим в f(x)u(x)+g(x)v(x)=d(x):
f(x)r(x)+g(x)[v(x)+f(x)q(x)]=d(x)
10
      Если общих делителей многочленов нулевой степени f(x) и g(x) не име-
ют, то они называются взаимно простыми.
      Определение. Наибольшим Общим Делителем отличных от нуля много-
членов f(x) и g(x) называется такой многочлен d(x), который является их общим
делителем и, вместе с тем, сам делится на любой другой общий делитель этих
многочленов.
      Обозначение: НОД (f(x),g(x))
      Вопрос: Существует ли НОД ?
            Да, способ отыскания – метод последовательного деления

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

      Даны: f(x), g(x).
      Найти НОД.
      Делим f(x) на g(x), получаем r1(x) делим g(x) на r1(x), получаем r2(x), r1(x)
на r2(x) –> r3(x) степени остатков все время понижаются => дойдем до такого
места, на котором деление совершается нацело => процесс остановиться.
      Тот остаток rк(x), на который нацело делится предыдущий остаток rк-1(x)
и будет НОД f(x) и g(x).
      f(x)=g(x)g1(x)+r1(x)
      g(x)=r1(x)q2(x)+r2(x)
      r1(x) =r2(x)q3(x)+r3(x)
      …
      rk-3(x) =rk-2(x)qk-1(x)+rk-1(x)
      rk-2(x) =rk-1(x)qk(x)+rk(x)
      rk-1(x) =rk(x)qk+1(x) => rk(x) НОД
      Если d(x) – НОД f(x) и g(x) => cd(x), c≠0 – НОД (f(x), g(x));
      Можно условиться, что старший коэффициент НОД - а будем считать
равным единице.
      Утверждение. Два многочлена взаимно просты               если их НОД=1
      Теорема. Если d(x)=НОД(f(x),g(x)) => можно найти такие многочлены
u(x) и v(x) : f(x)u(x)+g(x)v(x)=d(x). Можно при этом считать степени многочле-
нов f(x) и g(x) больше 0, что степень u(x) меньше степени g(x), а степень v(x)
меньше степени f(x).
      Доказательство основано на алгоритме Евклида. Если мы учтем, что
rk(x)=d(x) и положим u1(x)=1, v1(x)=-qk(x) то из предпоследнего равенства сле-
дует:
      d(x)=rk-3(x)u2(x)+ rk-2(x)v2(x), где u2(x)=v1(x), v2(x)=u1(x)-v1(x)qk-1(x)
      Продолжая подниматься по равенствам вверх, мы придем к доказывае-
мому.
      Пусть u(x) и v(x) уже найдены, но предположим что deg(u(x))≥deg(g(x))
делим u(x) на g(x): u(x)=g(x)q(x)+r(x), где deg(r(x))

Страницы