Полная версия

Главная arrow Математика, химия, физика arrow АЛГЕБРА И ТЕОРИЯ ЧИСЕЛ. ГРУППЫ, КОЛЬЦА И ПОЛЯ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

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

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

Определим норму целого числа а Ф 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 = a- bq, получим a-bq + г, где 0 < г < b = | b |.

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

Единственность. Пусть a-bq + r, где 0 < г < | b |, и а = bqх + гь где 0 < гх < | b|. Тогда bq + г - bqx + гь и если г = гь то получаем q = qx, что доказывает единственность. Предположим, что г Ф гь пусть гх < г. Тогда 0 1-bq1-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. Пусть dx = аиг + bvx. Легко видеть, что dx : d, откуда d < dl. Следовательно, d = dv

  • (2 => 3) Пусть dx = auj + bvx — наименьшее натуральное число множества М = {ax + by х, у е Z}. Докажем, что dx есть общий делитель целых чисел а и Ь. Разделим а на d1 с остатком: a = dxq + г, где 0 < г < dv Если предположить, что г Ф 0, то получаем г = а - dxq - a- (aua + bvx)q = a(l - uaq) + b(l - vxq) e e M, что противоречит минимальности числа dx в М. Следовательно, г = 0 и а : dj. Аналогично b I dx. Поскольку d1 = аиг + bvx, то dx делится на любой общий делитель d чисел а и Ь.
  • (3 => 1) Пусть d2 — натуральный общий делитель чисел а и Ь, который делится на любой общий делитель этих чисел, a d — наибольший из общих делителей данных чисел. Тогда d2 С другой стороны, по условию, d2 : d, откуда d < d2. Следовательно, d2 = d. Теорема доказана.

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

Пример 3.1

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>