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

В абстрактной алгебре евклидово кольцо (эвклидово кольцо) — кольцо, в котором существует аналог алгоритма Евклида.

Определение

Евклидово кольцо — это область целостности R, для которой определена евклидова функция (евклидова норма) $d: R \to \mathbb{N} \cup \{-\infty\}$, причём $d(a)=-\infty \Leftrightarrow a=0$, и возможно деление с остатком, по норме меньшим делителя, то есть для любых $a,b\in R,\, b\ne 0$ имеется представление $a=bq+r$, для которого $d(r)<d(b)$.

Замечание

Часто на евклидову норму накладывают дополнительное ограничение: $d(a)\le d(ab)$ для любых a и ненулевых b из кольца R. Если на R задана норма, не удовлетворяющая этому условию, её можно поправить, переопределив:

$d'(a) = \min_{x\in R\setminus\{0\}} d(ax)$

Такая норма нужному неравенству удовлетворяет, однако прежний алгоритм деления с остатком уже не годится — его тоже надо поправлять. Пусть $x\in R$ таков, что $d'(b) = d(bx)$. Разделим с остатком ax на bx: $ax = bxq' + r'x$, где $r' = a - bq'$ и $d(r'x)<d(bx)=d'(b)$. Так как из определения $d'(r')\le d(r'x)$, мы получили представление $a = bq' + r'$ с $d'(r')<d'(b)$, что и требовалось.

Тем не менее, преимуществ у такой нормы не так много — все обратимые элементы имеют одно и то же значение нормы, причём минимальное из всех (конечных), собственные делители элемента a имеют меньшее значение нормы, а также упрощается непосредственное доказательство факториальности евклидовых колец (без ссылки на факториальность колец главных идеалов, доказательство чего требует применения трансфинитной индукции). Основные же свойства евклидовых колец остаются в силе и без этого дополнительного свойства.

Примеры

• Кольцо целых чисел $\mathbb{Z}$. Пример евклидовой функции — абсолютная величина $|\cdot|$.
• Кольцо целых гауссовых чисел $\mathbb{Z}[i]$ (где i — мнимая единица, $i^2 = -1$) с нормой $d(a+ib) = a^2 + b^2$ — евклидово.
• Произвольное поле $K$ является евклидовым кольцом с нормой, равной 1 для всех элементов, кроме 0.
• Кольцо многочленов в одной переменной $K[x]$ над полем $K$. Пример евклидовой функции — степень deg.
• Кольцо формальных степенных рядов $K[[x]]$ над полем K является евклидовым кольцом. Норма степенного ряда — номер первого ненулевого коэффициента в нём (для нулевого ряда норма равна минус бесконечности).
  • Более общо, всякое локальное кольцо является евклидовым, если в нём максимальный идеал является главным и пересечение всех его степеней состоит только из нуля. Норма обратимого элемента равна 0, необратимого ненулевого — равна максимальной степени максимального идеала, которая содержит данный элемент, а норма нуля — минус бесконечность.
• Кольцо функций H(K), голоморфных на связном компакте K в C (каждая из них должна быть голоморфна в какой-нибудь окрестности этого компакта; две такие функции считаются равными в H(K), если они совпадают в некоторой окрестности K), тоже евклидово. За норму ненулевой функции принимается число нулей (с учётом кратности), которые она принимает на K.
• Счётное пересечение евклидовых колец (подколец в каком-нибудь кольце) не обязано быть евклидовым кольцом (и даже нётеровым или факториальным). Например, кольцо функций H(D), голоморфных в открытом круге D, является пересечением евклидовых колец функций H(K), голоморфных на замкнутых кругах K, содержащихся внутри D (см. предыдущий пример), однако оно ни нётерово, ни факториально, соответственно, и неевклидово.
• Кольцо частных S⁻¹R евклидова кольца R по мультипликативной системе S тоже является евклидовым. Нормой дроби x из S⁻¹R принимается

$d_S(x) = \min\{d_R(u):\,(u,s)\in R\times S, \, x=u/s\}$, где $d_R$ — евклидова норма в R, а $d_S$ — норма в S⁻¹R.

Деление с остатком определяется так. Пусть есть две ненулевые дроби $x=r/t$ и $y$ из S⁻¹R. По определению нормы в S⁻¹R существует элементы u в R и s в S, такие что $y=u/s$ и $d_S(y) = d_R(u)$. Произведём деление с остатком в кольце R элементов rs и u:
rs = uq + r', так что $d_R(r')<d_R(u)$. Тогда $r/t = (u/s)(q/t) + r'/ts$. Из построения следуют неравенства $d_S(r'/ts)\le d_R(r')< d_R(u) = d_S(y)$.

• Евклидовым является кольцо конечных десятичных дробей, так как оно является кольцом частных кольца целых чисел $\mathbb{Z}$.
• Евклидовыми являются кольца рациональных функций над полем $\mathbb{C}$ с фиксированными полюсами, так как такие кольца являются кольцами частных кольца многочленов $\mathbb{C}[x]$.

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

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

Свойства евклидовых колец

• В евклидовом кольце каждый идеал — главный (в частности, все евклидовы кольца нётеровы).
  • Пусть I — произвольный идеал в евклидовом кольце. Если он содержит лишь 0, — он главный. В противном случае среди его ненулевых элементов найдётся элемент f с минимальной нормой (принцип минимума для натуральных чисел). Он делит все остальные элементы идеала: Если g — произвольный элемент идеала I, представим его в виде g = fq + r с d(r)<d(f). Тогда r - тоже элемент идеала I и он обязан быть нулём, так как его норма меньше, чем у f. Следовательно, идеал I содержится в идеале (f). С другой стороны, всякий идеал, содержащий элемент f, содержит идеал (f). Значит, I = (f) - главный идеал.
• Каждое евклидово кольцо факториально, то есть каждый элемент представим конечным произведением простых элементов, и притом однозначно (с точностью до их перестановки и умножения на обратимые элементы). Факториальность - общее свойство всех колец главных идеалов.
• Каждое евклидово кольцо R целозамкнуто, то есть если дробь $a/b,\,a,b\in R$, является корнем многочлена $f\in R[x]$ со старшим коэффициентом, равным 1, тогда $a$ делится на $b$. Целозамкнутость - общее свойство всех факториальных колец.

Свойства модулей над евклидовым кольцом

Пусть R - евклидово кольцо. Тогда конечнопорождённые R-модули обладают следующими свойствами:

• Всякий подмодуль N конечнопорождённого R-модуля M конечно порождён. (следствие нётеровости кольца R)
• Ранг подмодуля N не превосходит ранга модуля M. (следствие главности идеалов в R)
• Подмодуль свободного R-модуля свободен. (то же)
• Гомоморфизм $A: N\to M$ конечнопорождённых R-модулей всегда приводится к нормальной форме. То есть существуют образующие (базис, если модуль свободен) $u_1, u_2, \dots, u_n$ модуля N, образующие (базис) $v_1, v_2, \dots, v_m$ модуля M, номер $k\le \min\{m,n\}$ и $a_1,\dots,a_k$ - элементы кольца R, такие что $a_i$ делит $a_{i+1}$ и при i>k $Au_i = 0$, а при остальных — $Au_i = a_iv_i$. При этом коэффициенты $a_1,\dots,a_k$ определены однозначно с точностью до умножения на обратимые элементы кольца R. (Тут прямо задействована евклидовость кольца R.)

См. также

• Кольцо
• Евклидово поле
• Область цельности
• Алгоритм Евклида
• Евклид

Ссылки

• Weisstein, Eric W. Евклидово кольцо (англ.) на сайте Wolfram MathWorld.
• Б. Л. ван дер Варден, «Алгебра», ISBN 5-8114-0552-9
• J. von zur Gathen, J. Gerhard, «Modern Computer Algebra», ISBN 0-521-82646-2