Евклидовы кольца

Определение:

Евклидово кольцо - кольцо, в котором существует алгоритм евклида.

Определение:

Евклидово кольцо - это область целостности [math]R[/math], для которой определена евклидова норма [math]\|\cdot \| :R \rightarrow \mathbb{N}\cup\{-\infty\}[/math], причем [math]\|a\|=-\infty \Leftrightarrow a=0[/math], для [math]\forall a,b\in R \exists[/math] представление [math]a=b\cdot q + r, для которого \|r\|\lt \|d\|[/math]

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

Изначально даны [math]a,b\in R[/math], необходимо найти их НОД. Пусть [math]a\lt b[/math]. Поделим [math]b[/math] на [math]a[/math] с остатком
[math]b=a\cdot u_1 + r_1 (0\le r_1\lt a)[/math],
[math]a=r_1\cdot u_2 + r_2 (0\le r_2\lt r_1)[/math],
...........................
[math]r_{n-1}=r_n\cdot u_{n+1} + r_{n+1} (0\le r_{n+1}\lt r_n)[/math],
[math]r_n=r_{n+1}\cdot u_{n+2}[/math].
Число [math]r_{n+1}[/math] является НОД чисел [math]a[/math] и [math]b[/math]. Алгоритм заканчивает свою работу, поскольку [math]\forall a \in \mathbb{N} \cup \{-\infty\}[/math] может строго превосходить лишь конечное количество других таких чисел.