Евклидовы кольца. 
Алгебра и теория чисел. 
Группы, кольца и поля

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

Вспомним, что для натуральных чисел а и 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. Докажем, что тогда г_п = НОД (а, Ь).

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

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

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

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

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

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