logo
Математический анализ 1

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

В евклидовом кольце осуществим алгоритм Евклида нахождения наибольшего общего делителя двух чисел (элементов). Пусть изначально даны два элемента a0 иa1, причём   и  . Деление с остатком даёт элемент   с  . Если он не равен нулю, можно опять применить деление с остатком, и получить элемент  , и т. д. Таким образом генерируется цепочка значений   с  . Однако эта цепочка прерывается, поскольку всякое число из   может строго превосходить лишь конечное количество других таких чисел. Это означает, что при некотором n остаток an+1 равен нулю, а an не равен, он и есть НОД элементов a0 и a1. Следовательно, в евклидовом кольце гарантировано завершение алгоритма Евклида. Строго говоря, именно в евклидовых кольцах и возможна реализация алгоритма Евклида.