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

Определение

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

Дополнительное ограничение

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

${\displaystyle d'(a)=\min _{x\in R\setminus \{0\}}d(ax)}$ .

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

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

Примеры

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

${\displaystyle d_{S}(x)=\min\{d_{R}(u):\,(u,s)\in R\times S,\,x=u/s\},}$

где ${\displaystyle d_{R}}$ — евклидова норма в ${\displaystyle R}$ , а ${\displaystyle d_{S}}$ — норма в ${\displaystyle S^{-1}R}$ .

Деление с остатком определяется следующим образом: пусть есть две ненулевые дроби ${\displaystyle x=r/t}$ и ${\displaystyle y}$ из S ⁻¹ R . По определению нормы в ${\displaystyle S^{-1}R}$ существует элементы ${\displaystyle u}$ в ${\displaystyle R}$ и ${\displaystyle s}$ в ${\displaystyle S}$ , такие, что ${\displaystyle y=u/s}$ и ${\displaystyle d_{S}(y)=d_{R}(u)}$ . Произведя деление с остатком в кольце ${\displaystyle R}$ элементов ${\displaystyle rs}$ и ${\displaystyle u}$ — ${\displaystyle rs=uq+r}$ , так что ${\displaystyle d_{R}(r')<d_{R}(u)}$ , получается ${\displaystyle r/t=(u/s)(q/t)+r'/ts}$ ; из построения следуют неравенства ${\displaystyle d_{S}(r'/ts)\leqslant d_{R}(r')<d_{R}(u)=d_{S}(y)}$ .

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

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

В евклидовом кольце осуществим алгоритм Евклида нахождения наибольшего общего делителя двух чисел (элементов). Пусть изначально даны два элемента ${\displaystyle a_{0}}$ и ${\displaystyle a_{1}}$ , причём ${\displaystyle d(a_{1})\leqslant d(a_{0})}$ и ${\displaystyle a_{1}\neq 0}$ . Деление с остатком даёт элемент ${\displaystyle a_{2}=a_{0}-a_{1}q_{1}}$ с ${\displaystyle d(a_{2})<d(a_{1})}$ . Если он не равен нулю, можно опять применить деление с остатком, и получить элемент ${\displaystyle a_{3}=a_{1}-a_{2}q_{2}}$ , и так далее. Таким образом генерируется цепочка значений ${\displaystyle a_{0},a_{1},a_{2},\dots }$ с ${\displaystyle d(a_{0})>d(a_{1})>d(a_{2})>\dots }$ . Однако эта цепочка прерывается, поскольку всякое натуральное число может строго превосходить лишь конечное количество других натуральных чисел. Это означает, что при некотором ${\displaystyle n}$ остаток ${\displaystyle a_{n+1}}$ равен нулю, а ${\displaystyle a_{n}}$ не равен, он и есть наибольший общий делитель элементов ${\displaystyle a_{0}}$ и ${\displaystyle a_{1}}$ . Следовательно, в евклидовом кольце гарантировано завершение алгоритма Евклида. Строго говоря, именно в евклидовых кольцах и возможна реализация алгоритма Евклида.

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

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

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

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

• Всякий подмодуль ${\displaystyle N}$ конечнопорождённого ${\displaystyle R}$ -модуля ${\displaystyle M}$ конечно порождён (следствие нётеровости кольца ${\displaystyle R}$ ).
• Ранг подмодуля ${\displaystyle N}$ не превосходит ранга модуля ${\displaystyle M}$ (следствие главности идеалов в ${\displaystyle R}$ — структурная теорема для конечнопорожденных модулей над областями главных идеалов ).
• Подмодуль свободного ${\displaystyle R}$ -модуля также свободен.
• Гомоморфизм ${\displaystyle A\colon N\to M}$ конечнопорождённых ${\displaystyle R}$ -модулей всегда приводится к нормальной форме. То есть существуют образующие (базис, если модуль свободен) ${\displaystyle u_{1},u_{2},\dots ,u_{n}}$ модуля N , образующие (базис) ${\displaystyle v_{1},v_{2},\dots ,v_{m}}$ модуля M , номер ${\displaystyle k\leqslant \min\{m,n\}}$ и ${\displaystyle a_{1},\dots ,a_{k}}$ — элементы кольца ${\displaystyle R}$ , такие, что ${\displaystyle a_{i}}$ делит ${\displaystyle a_{i+1}}$ и при i > k ${\displaystyle Au_{i}=0}$ , а при остальных — ${\displaystyle Au_{i}=a_{i}v_{i}}$ . При этом коэффициенты ${\displaystyle a_{1},\dots ,a_{k}}$ определены однозначно с точностью до умножения на обратимые элементы кольца ${\displaystyle R}$ . (В этом свойстве прямо задействована евклидовость кольца ${\displaystyle R}$ .)

См. также

• Евклидово поле
• Область целостности

Примечания

Ссылки

• 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 .