Евклидовы кольца

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

Вспомним, что для натуральных чисел а и b можно найти НОД(а, Ь) не только с помощью разложения данных чисел на простые множители, но и с помощью алгоритма Евклида. Составной частью алгоритма Евклида является деление с остатком. Разделить с остатком целое число а на целое число Ъ Ф 0 — значит найти неполное частное q и остаток г, такие что a = bq + г, причем остаток г должен удовлетворять условию 0 < г < Ь |.

Например, -273 = 23 • (-12) + 3, следовательно, при делении числа а = -273 на b = 23 получаем неполное частное q = -12 и остаток г = 3.

В произвольной области целостности нет отношения «меньше». Поэтому, обобщая деление с остатком на область целостности, мы применим маленькую хитрость: свяжем с каждым элементом а ^ 0 целое неотрицательное число h(a). Дадим соответствующее определение.

Определение ЗЛО. Евклидовым кольцом называется область целостности К, в которой для всякого элемента а * 0 однозначно определено целое неотрицательное число й(а), называемое нормой элемента а, такое что:

  • 1) h(.ab) > На), ИЮ;
  • 2) для любых элементов а и Ъ Ф 0 из К существуют элементы q, г е К, такие что а = bq + г, причем либо г = 0, либо h(г) < h(b) (возможность деления с остатком).

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

Определение 3.11. Алгоритм Евклида, примененный к элементам а Ф 0 и Ъ 0 евклидова кольца К, состоит в следующем:

  • 1) а делим на Ъ с остатком (начало алгоритма);
  • 2) если остаток отличен от нуля, то делитель делим на остаток (шаг алгоритма).

Следуя этому предписанию, выпишем шаги алгоритма:

Поскольку нормы остатков строго убывают, являясь целыми неотрицательными числами, то алгоритм Евклида конечен и закончится, когда мы получим остаток, равный нулю. Пусть гп+1 = 0. Докажем, что тогда гп = НОД(а, Ь).

Рассмотрим равенства алгоритма Евклида снизу вверх. Из последного равенства гп_г = rnqn+1 видим, что гп_г : г„. Но тогда из предпоследнего равенства заключаем, что гп_2 : гп. Поднимаясь по равенствам снизу вверх, получаем, что гп является общим делителем элементов а и Ь.

Пусть d является общим делителем элементов а и Ъ. Рассматривая равенства алгоритма Евклида сверху вниз, последовательно заключаем, что все остатки делятся на d. Следовательно, гл : d. Таким образом, гп является наибольшим общим делителем элементов а и Ъ. В итоге получаем следующее утверждение.

Теорема 3.5. Пусть даны элементы аиЪ евклидова кольца К. Если а : Ь, то НОД(а, Ь) = Ъ. Если ни один из данных элементов не делится на другой, то применим к ним алгоритм Евклида и последний не равный нулю остаток в этом алгоритме равен НОД(а, Ь).

Докажем следующее утверждение.

Теорема 3.6 (о линейной форме НОД). Для любых элементов а и Ъ евклидова кольца К существуют элементы и, v е К, такие что НОД(а, Ъ) - а ? и + Ъ ? v.

Доказательство. Если один из элементов а, Ъ делится на другой, то утверждение очевидно. Пусть ни один из элементов а, b не делится на другой. Применим к ним алгоритм Евклида. Рассматривая равенства алгоритма сверху вниз, последовательно остатки выражаем через а и Ь. Из первого равенства находим r1-a-bq1 = a ? 1 + bC-qj). Из второго равенства находим г2 = Ъ - - raq2 = Ъ - (а - bq1)q2 = a(-q2) + b( 1 + цдД. И т.д., на последнем шаге получим искомую линейную форму НОД.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >