| Определение: |
| Евклидово кольцо - кольцо, в котором существует алгоритм евклида. |
| Определение: |
| Евклидово кольцо - это область целостности [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]\mathbb{Z}[/math], тогда [math]\|a\|=|a|[/math]
- [math]\mathbb{Q}[x][/math], тогда [math]\|f(x)\|=deg(f(x))[/math]
[math]|a\cdot b|^2=|a|^2\cdot |b|^2\geq |b|^2[/math], кроме того [math]\|a\cdot b\|\geq \|b\|=|b|^2 \Rightarrow \|a\cdot b\|=|a\cdot b|^2[/math]
- [math]\mathbb{Z}[i]: \|a+b\cdot i\|=a^2+b^2[/math], т.e. [math]\|z\|=|z|^2[/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] может строго превосходить лишь конечное количество других таких чисел.
