Математическая логика и теория алгоритмов. Стенюшкина В.А. - 94 стр.

       НОД двух полиномов в I[x], где I – область целостности и р2(х) ≠ 0, мо-
жно найти повторным применением алгоритма деления PDF, рассмотренного
ранее. Этот процесс называется алгоритмом Евклида для полиномов. При этом
имеет место следующая теорема.
       Теорема Пусть p1( x ), p2 ( x ) ∈ I [ x ], p2 ( x ) ≠ 0 , I – область целостности.
Тогда алгоритм Евклида дает НОД [р1(х), р2(х)] – это последний отличный от
нуля остаток ph(x).
       Последовательность остатков полиномов, полученная при выполнении
алгоритма Евклида, называется последовательностью полиномиальных остат-
ков.
       Два полинома р(х) и q(x)называются ассоциированными, если каждый из
них является скалярным кратным другого. Любой полином ассоциирован ровно
с одним нормированным полиномом. Поэтому, когда ph(x) нормирован, можно
говорить о единственном наибольшем общем делителе.

       Примечание В Z НОД двух целых чисел единствен среди положитель-
ных; если брать по абсолютной величине, то, например, числа 6 и 9 имеют
НОД: 3 и –3.
       Два полинома в I[x] называются взаимно простыми, если любой их
НОД – обратимая константа из I. В этом случае говорится, что единичный эле-
мент кольца I – их наибольший общий делитель.

        5.5 Алгоритм Евклида для полиномов над полем

      Теорема Пусть, p1( x ), p2 ( x ) ≠ 0 ∈ I [ x ], I – поле. Тогда существуют по-
линомы    u(x), v(x) ∈ I[x] такие, что

        р1(х) v(x) + р2(х) u(x)= ph(x)                               (5.3)

где ph(x)= НОД [р1(х), р2(х)].
         Следствие Для того, чтобы два полинома р1(х), р2(х) ∈ I[x], I – поле, бы-
ли взаимно простыми, необходимо и достаточно существования полиномов
u(x), v(x) ∈ I[x], таких, что р1(х) v(x) + р2(х) u(x)= 1.
         Примечание Если u(x), v(x) соответствуют следствию,то полиномы
u1( x ) = u( x ) − t( x ) p1( x ), v1( x ) = v( x ) + t( x ), p2 ( x ), t ∈ I [ x ] тоже соответст-
вуют следствию. Полиномы u(x), v(x) не единственны; они могут иметь произ-
вольно высокую степень, но ограниченную снизу.
         Теорема В условиях предыдущей теоремы существуют единственные
полиномы f(x), q(x), степени которых ниже степеней полиномов p1(x), p2(x) соо-
тветственно, для которых p1(x) q(x)+ p2(x) f(x) = ph(x),                          ph(x) = НОД [p1(x),
p2(x)].
         Конструктивное доказательство этой теоремы можно усмотреть из при-
веденного ниже расширенного алгоритма Евклида для полиномов.