[Править]Алгоритм Евклида

В евклидовом кольце осуществим алгоритм Евклида нахождения наибольшего общего делителя двух чисел (элементов). Пусть изначально даны два элемента a₀ и a₁, причём   и  . Деление с остатком даёт элемент a₂ = a₀ − a₁q₁ с d(a₂) < d(a₁). Если он не равен нулю, можно опять применить деление с остатком, и получить элемент a₃ = a₁ − a₂q₂, и т. д. Таким образом генерируется цепочка значений   с  . Однако эта цепочка прерывается, поскольку всякое число из   может строго превосходить лишь конечное количество других таких чисел. Это означает, что при некотором n остаток a_n+1 равен нулю, а a_n не равен, он и есть НОД элементов a₀ и a₁. Следовательно, в евклидовом кольце гарантировано завершение алгоритма Евклида. Строго говоря, именно в евклидовых кольцах и возможна реализация алгоритма Евклида.