Евклидово кольцо: различия между версиями

В евклидовом кольце осуществим [[алгоритм Евклида]] нахождения наибольшего общего делителя двух чисел (элементов). Пусть изначально даны два элемента ''a₀'' и ''a₁'', причём <math>d(a_1)\le d(a_0)</math> и <math>a_1\ne 0</math>. Деление с остатком даёт элемент <math>a_2 = a_0 - a_1q_1</math> с <math>d(a_2)<d(a_1)</math>. Если он не равен нулю, можно опять применить деление с остатком, и получить элемент <math>a_3 = a_1 - a_2q_2</math>, и т. д. Таким образом генерируется цепочка значений <math>a_0, a_1, a_2, \dots</math> с <math>d(a_0)>d(a_1)>d(a_2)>\dots</math>. Однако эта цепочка прерывается, поскольку всякое число из <math>N\cup\{-\infty\}</math> может строго превосходить лишь конечное количество других таких чисел. Это означает, что при некотором ''n'' остаток ''a_n+1'' равен нулю, а ''a_n'' не равен, он и есть НОД элементов ''a₀'' и ''a₁''. Следовательно, в евклидовом кольце гарантировано завершение алгоритма Евклида. Строго говоря, именно в евклидовых кольцах и возможна реализация алгоритма Евклида.

 

* Каждое евклидово кольцо ''R'' целозамкнуто, то есть если дробь <math>a/b,\,a,b\in R</math>, является корнем многочлена <math>f\in R[x]</math> со старшим коэффициентом, равным 1, тогда <math>a</math> делится на <math>b</math>. Целозамкнутость - общее свойство всех факториальных колец.