12.8. АЛГОРИТМ ЕВКЛИДА

На основном этапе декодирования альтернантных кодов используется алгоритм Евклида. Он является наиболее простым и прямым способом для вычисления наибольшего общего делителя двух целых чисел или двух многочленов или для представления действительного числа в виде цепной дроби.

Мы опишем этот алгоритм применительно к многочленам, так как этот случай представляет для нас наибольший интерес. Для применения алгоритма к целым числам требуются тривиальные изменения. В этом параграфе коэффициенты многочленов могут лежать в произвольном поле. Наибольшим общим делителем двух многочленов называется многочлен наивысшей степени, который делит одновременно и Умножение такого многочлена на произвольную константу также дает

Теорема 13. (Алгоритм Евклида для многочленов.) Для заданных многочленов таких, что выполним следующий ряд делений, выписанный в виде последовательности уравнений:

Полученный в процессе деления последний ненулевой остаток равен НОД многочленов

Доказательство. Очевидно, что делит следовательно, делит следовательно, делит оба многочлена Наоборот, если делит и то делит Следовательно, равен НОД многочленов

Пример. Найдем НОД многочленов над полем

Следовательно, равен НОД многочленов

В качестве побочного результата алгоритма Евклида получаем; следующую полезную теорему.

Теорема 14. Пусть такие многочлены, что и пусть — их НОД. Тогда существуют многочлены такие, что

причем степени меньше степени многочлена

Доказательство. Определим многочлены начальными условиями

и рекуррентными соотношениями

Тогда

Также

Определитель правой части в (12.61) равен Следовательно, из (12.61) и (12.62) имеем:

В частности,

что дает (12.58). Кроме того,

и аналогично для

Следствие 15. Если взаимно просты, то существуют такие многочлены что

Аналогичный результат, естественно, имеет место и для целых чисел.

Пример. Продолжая предыдущий пример, находим:

и согласно уравнению (12.58)

Упражнение. (22). Доказать, что взаимно просты.