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

Пусть даны мн-члены f(x) и g(x). Делим f(x) на g(x) и получаем некоторый остаток r₁(x). Делим затем g(x) на r₁(x) и получаем остаток r₂(x), делим r₁(x) на r₂(x) и т.д. Так как степени остатков все время понижаются, то в этой епочке последовательных делений мы должны дойти до такого места, на котором деление совешится нацело и поэтому процесс остановится. Тот остаток r_k(x), на кот наело делится предыдущий остаток r_k-1(x), и будет НОД'ом многочленов f(x) и g(x).