Евклидово кольцо
Евклидово кольцо — общеалгебраическое кольцо, в котором существует аналог алгоритма Евклида.
Определение
Евклидово кольцо — область целостности [math]\displaystyle{ R }[/math], для которой определена евклидова функция (евклидова норма) [math]\displaystyle{ d \colon R \setminus \{ 0 \} \to \mathbb N_0 }[/math], такая, что возможно деление с остатком по норме меньшим делителя, то есть для любых [math]\displaystyle{ a,b\in R,\, b\ne 0 }[/math] имеется представление [math]\displaystyle{ a=bq+r }[/math], для которого [math]\displaystyle{ d(r)\lt d(b) }[/math] или [math]\displaystyle{ r=0 }[/math][1].
Дополнительное ограничение
Часто на евклидову норму накладывают дополнительное ограничение: [math]\displaystyle{ d(a)\leqslant d(ab) }[/math] для любых ненулевых [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math] из кольца [math]\displaystyle{ R }[/math]. Если на [math]\displaystyle{ R }[/math] задана норма, не удовлетворяющая этому условию, её можно поправить, переопределив:
- [math]\displaystyle{ d'(a) = \min_{x\in R\setminus\{0\}} d(ax) }[/math].
Такая норма нужному неравенству удовлетворяет, однако прежний алгоритм деления с остатком требует поправки (для [math]\displaystyle{ x\in R }[/math] и [math]\displaystyle{ d'(b) = d(bx) }[/math] делится [math]\displaystyle{ ax }[/math] на [math]\displaystyle{ bx }[/math] с остатком: [math]\displaystyle{ ax = bxq' + r'x }[/math], где [math]\displaystyle{ r' = a - bq' }[/math] и [math]\displaystyle{ d(r'x)\lt d(bx)=d'(b) }[/math], а так как из определения следует [math]\displaystyle{ d'(r')\leqslant d(r'x) }[/math], получается искомое представление [math]\displaystyle{ a = bq' + r' }[/math] с [math]\displaystyle{ d'(r')\lt d'(b) }[/math]).
Преимуществ у такой нормы не так много — все обратимые элементы имеют одно и то же значение нормы, причём минимальное из всех (конечных), собственные делители элемента [math]\displaystyle{ a }[/math] имеют меньшее значение нормы, а также упрощается непосредственное доказательство факториальности евклидовых колец (без ссылки на факториальность колец главных идеалов, доказательство чего требует применения трансфинитной индукции). Основные же свойства евклидовых колец остаются в силе и без этого дополнительного свойства.
Примеры
- Кольцо целых чисел [math]\displaystyle{ \mathbb{Z} }[/math]. Пример евклидовой функции — абсолютная величина [math]\displaystyle{ |\cdot| }[/math].
- Кольцо целых гауссовых чисел [math]\displaystyle{ \mathbb{Z}[i] }[/math] (где [math]\displaystyle{ i }[/math] — мнимая единица, [math]\displaystyle{ i^2 = -1 }[/math]) с нормой [math]\displaystyle{ d(a+ib) = a^2 + b^2 }[/math] — евклидово.
- Произвольное поле [math]\displaystyle{ K }[/math] является евклидовым кольцом с нормой, равной 1 для всех элементов, кроме 0.
- Кольцо многочленов в одной переменной [math]\displaystyle{ K[x] }[/math] над полем [math]\displaystyle{ K }[/math]. Пример евклидовой функции — степень deg.
- Кольцо формальных степенных рядов [math]\displaystyle{ K[[x]] }[/math] над полем [math]\displaystyle{ K }[/math] является евклидовым кольцом. Норма степенного ряда — номер первого ненулевого коэффициента в нём.
- Более общо, всякое локальное кольцо является евклидовым, если в нём максимальный идеал является главным и пересечение всех его степеней состоит только из нуля. Норма обратимого элемента равна 0, необратимого ненулевого — максимальной степени максимального идеала, которая содержит данный элемент.
- Кольцо функций [math]\displaystyle{ H(K) }[/math], голоморфных на связном компакте [math]\displaystyle{ K }[/math] в [math]\displaystyle{ \Complex }[/math] (каждая из них должна быть голоморфна в какой-нибудь окрестности этого компакта; две такие функции считаются равными в [math]\displaystyle{ H(K) }[/math], если они совпадают в некоторой окрестности [math]\displaystyle{ K }[/math]), тоже евклидово. За норму ненулевой функции принимается число нулей (с учётом кратности), которые она принимает на [math]\displaystyle{ K }[/math].
- Счётное пересечение евклидовых колец (подколец в каком-нибудь кольце) не обязано быть евклидовым кольцом (и даже нётеровым или факториальным). Например, кольцо функций [math]\displaystyle{ H(\mathbb D) }[/math], голоморфных в открытом круге [math]\displaystyle{ \mathbb D }[/math], является пересечением евклидовых колец функций [math]\displaystyle{ H(K) }[/math], голоморфных на замкнутых кругах [math]\displaystyle{ K }[/math], содержащихся внутри [math]\displaystyle{ \mathbb D }[/math], однако оно ни нётерово, ни факториально, соответственно, и неевклидово.
- Кольцо частных [math]\displaystyle{ S^{-1}R }[/math] евклидова кольца [math]\displaystyle{ R }[/math] по мультипликативной системе [math]\displaystyle{ S }[/math] тоже является евклидовым. Нормой дроби [math]\displaystyle{ x }[/math] из [math]\displaystyle{ S^{-1}R }[/math] принимается:
- [math]\displaystyle{ d_S(x) = \min\{d_R(u):\,(u,s)\in R\times S, \, x=u/s\}, }[/math]
- где [math]\displaystyle{ d_R }[/math] — евклидова норма в [math]\displaystyle{ R }[/math], а [math]\displaystyle{ d_S }[/math] — норма в [math]\displaystyle{ S^{-1}R }[/math].
- Деление с остатком определяется следующим образом: пусть есть две ненулевые дроби [math]\displaystyle{ x=r/t }[/math] и [math]\displaystyle{ y }[/math] из S−1R. По определению нормы в [math]\displaystyle{ S^{-1}R }[/math] существует элементы [math]\displaystyle{ u }[/math] в [math]\displaystyle{ R }[/math] и [math]\displaystyle{ s }[/math] в [math]\displaystyle{ S }[/math], такие, что [math]\displaystyle{ y=u/s }[/math] и [math]\displaystyle{ d_S(y) = d_R(u) }[/math]. Произведя деление с остатком в кольце [math]\displaystyle{ R }[/math] элементов [math]\displaystyle{ rs }[/math] и [math]\displaystyle{ u }[/math] — [math]\displaystyle{ rs = uq + r }[/math], так что [math]\displaystyle{ d_R(r')\lt d_R(u) }[/math], получается [math]\displaystyle{ r/t = (u/s)(q/t) + r'/ts }[/math]; из построения следуют неравенства [math]\displaystyle{ d_S(r'/ts)\leqslant d_R(r')\lt d_R(u) = d_S(y) }[/math].
- Евклидовым является кольцо конечных десятичных дробей, так как оно является кольцом частных кольца целых чисел [math]\displaystyle{ \Z }[/math].
- Евклидовыми являются кольца рациональных функций над полем [math]\displaystyle{ \mathbb{C} }[/math] с фиксированными полюсами, так как такие кольца являются кольцами частных кольца многочленов [math]\displaystyle{ \mathbb{C}[x] }[/math].
Алгоритм Евклида
В евклидовом кольце осуществим алгоритм Евклида нахождения наибольшего общего делителя двух чисел (элементов). Пусть изначально даны два элемента [math]\displaystyle{ a_0 }[/math] и [math]\displaystyle{ a_1 }[/math], причём [math]\displaystyle{ d(a_1)\leqslant d(a_0) }[/math] и [math]\displaystyle{ a_1\ne 0 }[/math]. Деление с остатком даёт элемент [math]\displaystyle{ a_2 = a_0 - a_1q_1 }[/math] с [math]\displaystyle{ d(a_2)\lt d(a_1) }[/math]. Если он не равен нулю, можно опять применить деление с остатком, и получить элемент [math]\displaystyle{ a_3 = a_1 - a_2q_2 }[/math], и так далее. Таким образом генерируется цепочка значений [math]\displaystyle{ a_0, a_1, a_2, \dots }[/math] с [math]\displaystyle{ d(a_0)\gt d(a_1)\gt d(a_2)\gt \dots }[/math]. Однако эта цепочка прерывается, поскольку всякое натуральное число может строго превосходить лишь конечное количество других натуральных чисел. Это означает, что при некотором [math]\displaystyle{ n }[/math] остаток [math]\displaystyle{ a_{n+1} }[/math] равен нулю, а [math]\displaystyle{ a_n }[/math] не равен, он и есть наибольший общий делитель элементов [math]\displaystyle{ a_0 }[/math] и [math]\displaystyle{ a_1 }[/math]. Следовательно, в евклидовом кольце гарантировано завершение алгоритма Евклида. Строго говоря, именно в евклидовых кольцах и возможна реализация алгоритма Евклида.
Свойства евклидовых колец
- В евклидовом кольце каждый идеал — главный (в частности, все евклидовы кольца нётеровы).
- Пусть [math]\displaystyle{ I }[/math] — произвольный идеал в евклидовом кольце. Если он содержит лишь [math]\displaystyle{ 0 }[/math], — он главный. В противном случае среди его ненулевых элементов найдётся элемент [math]\displaystyle{ f }[/math] с минимальной нормой (принцип минимума для натуральных чисел). Он делит все остальные элементы идеала: представив произвольный элемент [math]\displaystyle{ g \in I }[/math] в виде [math]\displaystyle{ g = fq + r }[/math] с [math]\displaystyle{ d(r) \lt d(f) }[/math] получается, что [math]\displaystyle{ r }[/math] — тоже элемент идеала [math]\displaystyle{ I }[/math] и он обязан быть нулём, так как его норма меньше, чем у [math]\displaystyle{ f }[/math]. Следовательно, идеал [math]\displaystyle{ I }[/math] содержится в идеале [math]\displaystyle{ (f) }[/math]. С другой стороны, всякий идеал, содержащий элемент [math]\displaystyle{ f }[/math], содержит идеал [math]\displaystyle{ (f) }[/math], откуда следует, что [math]\displaystyle{ I = (f) }[/math] — главный идеал.
- Каждое евклидово кольцо факториально, то есть каждый элемент представим конечным произведением простых элементов, и притом однозначно (с точностью до их перестановки и умножения на обратимые элементы). Факториальность — общее свойство всех колец главных идеалов.
- Каждое евклидово кольцо [math]\displaystyle{ R }[/math] целозамкнуто, то есть если дробь [math]\displaystyle{ a/b,\,a,b\in R }[/math], является корнем многочлена [math]\displaystyle{ f\in R[x] }[/math] со старшим коэффициентом, равным 1, тогда [math]\displaystyle{ a }[/math] делится на [math]\displaystyle{ b }[/math]. Целозамкнутость — общее свойство всех факториальных колец.
Свойства модулей над евклидовым кольцом
Пусть [math]\displaystyle{ R }[/math] — евклидово кольцо. Тогда конечнопорождённые [math]\displaystyle{ R }[/math]-модули обладают следующими свойствами:
- Всякий подмодуль [math]\displaystyle{ N }[/math] конечнопорождённого [math]\displaystyle{ R }[/math]-модуля [math]\displaystyle{ M }[/math] конечно порождён (следствие нётеровости кольца [math]\displaystyle{ R }[/math]).
- Ранг подмодуля [math]\displaystyle{ N }[/math] не превосходит ранга модуля [math]\displaystyle{ M }[/math] (следствие главности идеалов в [math]\displaystyle{ R }[/math] — структурная теорема для конечнопорожденных модулей над областями главных идеалов).
- Подмодуль свободного [math]\displaystyle{ R }[/math]-модуля также свободен.
- Гомоморфизм [math]\displaystyle{ A \colon N\to M }[/math] конечнопорождённых [math]\displaystyle{ R }[/math]-модулей всегда приводится к нормальной форме. То есть существуют образующие (базис, если модуль свободен) [math]\displaystyle{ u_1, u_2, \dots, u_n }[/math] модуля N, образующие (базис) [math]\displaystyle{ v_1, v_2, \dots, v_m }[/math] модуля M, номер [math]\displaystyle{ k\leqslant \min\{m,n\} }[/math] и [math]\displaystyle{ a_1,\dots,a_k }[/math] — элементы кольца [math]\displaystyle{ R }[/math], такие, что [math]\displaystyle{ a_i }[/math] делит [math]\displaystyle{ a_{i+1} }[/math] и при i > k [math]\displaystyle{ Au_i = 0 }[/math], а при остальных — [math]\displaystyle{ Au_i = a_iv_i }[/math]. При этом коэффициенты [math]\displaystyle{ a_1,\dots,a_k }[/math] определены однозначно с точностью до умножения на обратимые элементы кольца [math]\displaystyle{ R }[/math]. (В этом свойстве прямо задействована евклидовость кольца [math]\displaystyle{ R }[/math].)
См. также
Примечания
- ↑ Курош, 1962, с. 91.
Ссылки
- Weisstein, Eric W. Евклидово кольцо (англ.) на сайте Wolfram MathWorld.
- Б. Л. ван дер Варден. Алгебра. — СПб.: Лань, 2004. — 624 с. — ISBN 5-8114-0552-9.
- Курош А. Г. Лекции по общей алгебре. — М.: Физматлит, 1962. — 400 с.
- Родосский К. А. Алгоритм Евклида. — М.: Наука, 1988. — 239 с.
- J. von zur Gathen, J. Gerhard. Modern Computer Algebra. — Cambridge University Press, 1999. — 771 p. — ISBN 0-521-82646-2.