Примеры евклидовых колец

Евклидовость кольца целых чисел

Определим норму целого числа а Ф 0, положив h (a) = |а|. Поскольку h (ab) = |а?>| > |а|, |Ь|, то свойство 1) из определения евклидова кольца выполнено (см. определение 3.10). Докажем возможность деления с остатком. Она вытекает из следующего более сильного утверждения.

Теорема ЗЛО. Для любых целых чисел a ub * 0 существуют и притом единственные целые числа qur, такие что a = bq + г и 0 <�г< Ь.

Доказательство. Существование. Рассмотрим случай Ъ > 0. Разобьем числовую прямую на отрезки длиной Ъ точками 0, ±Ъ, ±2Ь,… (рис. 3.1).

Рис. 3.1.

Где бы ни было расположено число а, оно обязательно попадет в один из данных отрезков. Причем можно считать, что а не совпадает с правым концом отрезка, так как если бы это произошло, то мы рассмотрели бы следующий отрезок, для которого а было бы левым концом. Пусть а попало в отрезок [bq, b (q + 1)]. Тогда bq < a < bq + b, откуда 0 < а — bq < b. Обозначив r = abq, получим a-bq + г, где 0 < г < b = | b |.

Теперь рассмотрим случай b < 0. Тогда -Ь > О и по доказанному существуют целые числа q иг, такие что а — (-Ь)? q + г, где 0 < г < | —Ь | = | Ъ |. Но тогда а = Ь ? (-q) + г, и существование доказано.

Единственность. Пусть a-bq + r, где 0 < г < | b |, и, а = bq_х + г_ь где 0 < г_х < | b|. Тогда bq + г — bq_x + г_ь и если г = г_ь то получаем q = q_x, что доказывает единственность. Предположим, что г Ф г_ь пусть г_х < г. Тогда 0 1-bq₁-bq: b — противоречие, ибо натуральное число г — г_х < |Ь| и не может делиться на Ь. Теорема доказана.

Вместе с тем доказана евклидовость кольца целых чисел, из которой следует факториальность этого кольца. В частности, доказана основная теорема арифметики.

Отметим, что стремление иметь единственный наибольший общий делитель двух целых чисел приводит к требованию, чтобы НОД был натуральным числом. В этой связи докажем эквивалентность трех возможных определений НОД как натуральных чисел.

Теорема 3.11. Для произвольных целых чисел аиЪ, неравных нулю одновременно, следующие утверждения эквивалентны:

• 1) d является наибольшим из общих делителей чисел aub;
• 2) d есть наименьшее натуральное число вида аи + bv, где и,

v е Z;

3) d есть натуральный общий делитель чисел, а и Ь, который делится на любой общий делитель этих чисел.

Доказательство. (1 => 2) Пусть d является наибольшим из общих делителей чисел а и Ь. Тогда d = НОД (а, Ь) и существуют целые числа и, v е Z, такие что d — аи + bv (линейная форма НОД). Следовательно, de М = {ах + Ьу х, у е Z}, и если dj есть наименьшее натуральное число множества М, то d_х < d. Пусть d_x = аи_г + bv_x. Легко видеть, что d_x: d, откуда d < d_l. Следовательно, d = d_v

• (2 => 3) Пусть d_x = auj + bv_x — наименьшее натуральное число множества М = {ax + by х, у е Z}. Докажем, что d_x есть общий делитель целых чисел а и Ь. Разделим а на d₁ с остатком: a = d_xq + г, где 0 < г < d_v Если предположить, что г Ф 0, то получаем г = а — d_xq — a- (au_a + bv_x)q = a (l — u_aq) + b (l — v_xq) e e M, что противоречит минимальности числа d_x в М. Следовательно, г = 0 и а: dj. Аналогично b I d_x. Поскольку d₁ = аи_г + bv_x, то d_x делится на любой общий делитель d чисел а и Ь.
• (3 => 1) Пусть d₂ — натуральный общий делитель чисел а и Ь, который делится на любой общий делитель этих чисел, a d — наибольший из общих делителей данных чисел. Тогда d₂ С другой стороны, по условию, d₂: d, откуда d < d₂. Следовательно, d₂ = d. Теорема доказана.

Покажем на примере, как реализуется алгоритм Евклида в кольце целых чисел.

Пример 3.1.

Таким образом, Н0Д (21 125, 9061) = -175а + 408Ь.