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

Пусть — коммутативное кольцо. ЛЕММА 2.5. Пусть в коммутативном кольце для элементов a, b, q и выполняется равенство

тогда

Доказательство. Пусть . Так как то ввиду . Поскольку d есть общий делитель b и , то . Аналогично убеждаемся, что . Следовательно,

Для нахождения НОД двух элементов кольца полиномов (или любого евклидова кольца) применяют способ «последовательного деления», называемый алгоритмом Евклида.

Смысл этого способа состоит в сведении вычисления НОД данных полиномов а, b из к вычислению полиномов с меньшими степенями.

Предположим, что ни один из полиномов а, b не делится (в ) на другой, и положим тогда

Продолжаем этот процесс до тех пор, пока не получим при делении нулевой остаток:

Этот процесс последовательного деления называется алгоритмом Евклида.

Отметим, что последовательность есть убывающая последовательность натуральных чисел. Поэтому она обрывается через конечное число шагов. Предположим, что тогда

На основании леммы 2.5 из выписанных выше равенств следует:

Таким образом, НОД есть НОД

Мы пришли к следующему выводу. Если к полиномам а и b кольца применить алгоритм Евклида, то получающийся при этом последний ненулевой остаток есть НОД полиномов а и b.

СЛЕДСТВИЕ 2.6. Пусть — подполе поля — кольца полиномов соответственно над и над Пусть а и b — не равные одновременно нулю полиномы из Если d и в — нормированные наибольшие общие делители полиномов а и b соответственно в то