Основные алгебраические структуры (стр. 29 )

Доказательство. Если а - обратим (левая часть эквиваленции (5)), то он подпадает под условие свойства 1, откуда следует правая часть (5). Если же выполняется правая часть эквиваленции (5), то элемент а подпадает под условие свойства 2, откуда вытекает факт левой части (5).

Замечание. Доказанный критерий обратимости элементов евклидова кольца хорошо просматривается на приведенных выше примерах евклидовых колец.

Теорема. Всякое евклидово кольцо является кольцом главных идеалов.

Доказательство. Пусть R - евклидово кольцо и φ - его статма. Возьмем произволный идеал I кольца R. Наша цель - показать, что I - главный идеал. Считаем, что I отличен от несобственных идеалов 0R и 1R, являющихся главными по определению. Пусть I* - множество ненулевых элементов идеала I. I* не пусто, ибо I ≠ 0R. Рассмотрим множество натуральных чисел φ(I*):

φ(I*) = {φ(x)|xI*} N (6)

Пусть m наименьшее натуральное число из φ(I*):

m = min φ(I*) (7)

Пусть, далее, a I* - один из прообразов числа m относительно φ:

φ(а) = m (8)

Возьмем теперь произвольный элемент хI и разделим его евклидово на а:

x = aq + r, r = o φ(r) < φ(a) (9)

Оценим возможные исходы для остатка r из числа представленных в (9). Во - первых, заметим, что равенство (9) гарантирует попадание r в идеал I. Далее, если r ≠ 0, то неравенство φ(r) < φ(a) - согласно (7), (8) - противоречит выбору а. Следовательно, единственный исход для r - это r = 0. При этом (9) указывет на R-кратность элемента х элементу а, что - в иной редакции - прочитывается как I = aR, т. е., I - главный идеал.

Комментарий. Доказанная теорема наделяет евклидово кольцо статусом кольца главных идеалов а - следовательно - и статусом факториального кольца (см. §5). Таким образом, по умолчанию считается, что в евклидовом кольце действительны эффективные процедуры нахождения НОД и НОК двух элементов либо по типу факториального кольца, либо по типу кольца главных идеалов.

§7. Алгоритм Евклида нахождения НОД двух элементов евклидова кольца

Пусть R - евклидово кольцо со статмой φ. Кроме двух процедур нахождения НОД двух элементов, указанных в комментарии §6, в евклидовом кольце имеется еще одна - третья - процедура нахождения НОД, обеспеченная ресурсами R как евклидова кольца. Построим ее.

Возьмем два произвольных элемена a и b кольца R. Ищем их НОД. Мы усилим замечание 1 §7 Главы II и будем считать оба элемента a и b ненулевыми: a, b R*. Иные варианты имеют достаточно очевидный ответ. ‍Если один из этих элементов делит другой - например, a|b, - то ответ очевиден (см. §7 Главы II, свойство 2 НОД): (a, b) = a. Поэтому, в дальнейших рассуждениях мы исходим из того, что элементы a и b не делят друг друга: a|b и b|a (верхний индекс n у знака делимости «|» означает «не делит»: англ. not - не).

Разделим евклидово a на b:

a = bq‍ + r (1)

Поскольку b|a, в равенстве (1) остаток r ≠ 0. Поэтому, согласно определению евклидова кольца (см. (2) §6), мы фиксируем:

φ(b) > φ(r) (2)

Так как r ≠ 0, то выполнимо евклидово деление элемента b на r. Реализуем это деление:

b = (r)q + r (1)

Если если остаток r равен нулю, мы заканчиваем процедуру евклидовых делений. Если же r ≠ 0, то вновь, согласно определению евклидова кольца, мы фиксируем:

φ(r) > φ(r) (2)

То, что r ≠ 0, гарантирует продолжение проводимой процедуры евклидовых делений: мы можем евклидово разделить r на r и, получив остаток r:

r = (r)q + r (1)

После чего предпринять дальнейшие шаги: если r = 0 - процедуру евклидовых делений заканчиваем; если же r ≠ 0, то мы фиксируем:

φ(r) > φ(r) (2)

и делим евклидово r на r с получением следующего остатка r и т. д. Оценим возникающую ситуацию евклидовых делений. Ненулевые остатки r, r, r, . . . порождают неравенства (2) натуральных чисел, которые можно объединить в одну убывающую последовательность:

φ(b) > φ(r) > φ(r) > φ(r) ˃ . . . (3)

Убывающая последовательность (3) натуральных чисел ограничена сверху числом φ(b) и потому обязательно конечна. А это - прямое указание на то, что не может быть бесконечной последовательность ненулевых остатков r, r, r, . . .. Иными словами, на некотором шаге произведя соответствующее евклидово деление, мы с неизбежность получим нулевой остаток. Обозначим последний ненулевой остаток при евклидовых делениях типа (1) через r - т. е., следующий остаток r = 0 - и выпишем два последних евклидовых деления:

r = (r)q + r (1)

r = (r)q (r = 0) (1)