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

 

Рассмотрим алгоритм Евклида только для целых чисел. На многочлены алгоритм Евклида распространяется аналогичным образом, т. к. они, как и целые числа, обладают свойством евлидовости - их можно делить с остатком. Разделить целое число на число с остатком - это значит найти такие числа и (, арии которых выполняется равенство .

Нахождение наибольший общий делитель двух многочленов состоит в следующем. Выполним цепочку делений с остатком: , ; , ; , ; …; , , .

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