Расширенный алгоритм Евклида и его применение.

Date: 2015-10-07; view: 523.

Примеры

Идеал в кольце.

Евклидово кольцо.

{(1) – стр. 101}
Коммутативное кольцо R называется евклидовым , если для него выполнены следующие свойства:

· Кольцо R — целостное (т. е. в нём нет делителей нуля: из ab = 0 следует, что a = 0 или b = 0).

· Для каждого ненулевого элемента кольца определена числовая характеристика — норма, которая принимает целые неотрицательные значения. Т. е. норма — это такое отображение N : R \ {0} → Z, что N (r) r 0.

· Возможность деления с остатком означает, что для любых элементов a, b кольца, b ≠ 0, существуют такие q, r, что a = qb + r и либо r = 0, либо N (r) < N (b). Элемент r называется остатком от деления a на b. Это основное свойство нормы.

· Норма произведения двух ненулевых сомножителей больше либо равна норме любого из сомножителей. Формально: для любых a, b ∈ R, a ≠ 0, b ≠ 0 выполнено N (ab) r max(N (a), N (b)).

{(1) – стр. 93}
Подмножество I ∈ R называется левым идеалом , если выполняются два следующих условия:

· если a, b ∈ I , то a − b ∈ I;

· если a ∈ I, r ∈ R, то ra ∈ I .

Аналогично определяются правые и двусторонние идеалы.

{(3) – слайд 86}
Задача вычисления НОД(a, b) натуральных чисел a и b (a r b).
Если d – общий делитель пары чисел (a, b), то d является общим делителем для чисел (a – b, b). Отсюда:

a. пары чисел (a, b) и (a – kb, b) (k ∈ Z) имеет одинаковые общие делители;

b. вместо a - kb можно взять остаток r₀ от деления нацело a на b: a = bq + r₀, q ∈ Z, 0 ≤ r₀ < b;

c. затем, переставив числа в паре, можно повторить процедуру; она закончится, т.к. числа в паре уменьшаются, но остаются неотрицательными.

В результате: за конечное число шагов образуется пара (r_n, 0).Ясно, что НОД(a, b) = r_n.
Для нахождения по паре натуральных чисел (a; b) натурального d и пары целых (x, y) таких, что
d = НОД(a, b) = ax + ay, применяют расширенный алгоритм Евклида.
Расширенный алгоритм Евклида повторяет схему простого метода, в котором на каждом шаге:

§ дополнительно вычисляются x_i и y_i по формулам

§ справедливо соотношение

Алгоритм Евклида и его расширенная версия остаётся справедливым в любом евклидовом кольце, следовательно, и в любом поле Галуа. Поэтому: обратный элемент y(x) для некоторого многочлена b(x) в поле определяется соотношением

Оно может быть решено путем применения расширенного алгоритма Евклида для пары многочленов (a; b) в поле F. Решение данных уравнений существует всегда: поскольку a — неприводимый многочлен и