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

Если каждый из двух многочленов делится без остатка на третий, то этот третий многочлен называется общим делителем первых двух.

Наибольшим общим делителем (НОД) двух многочленов называется их общий делитель наибольшей степени.

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

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

Алгоритм Евклида реализуется в виде последовательности делений. В первом делении многочлен большей степени рассматривается как делимое, а меньшей – как делитель. Если многочлены, для которых находится НОД, имеют одинаковые степени, то делимое и делитель выбираются произвольно.

Если при очередном делении многочлен в остатке имеет степень больше или равную 1, то делитель становится делимым, а остаток – делителем.

Если при очередном делении многочленов получен остаток, равный нулю, то НОД данных многочленов найден. Им является делитель при последнем делении.

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