§ 11. Алгоритм Евклида

В этом параграфе будет изложен эффективный алгоритм нахождения НОД(f, g) двух многочленов f(x) и g(x)  0.

С

f(x) = g(x)q₀(x) + r₀(x), d(r₀) < d(g),

g(x) = r₀(x)q₁(x) + r₁(x), d(r₁) < d(r₀),

r₀(x) = r₁(x)q₂(x) + r₂(x), d(r₂) < d(r₁),

… … … … …

r_s–2(x) = r_s–1(x)q_s(x) + r_s(x), d(r_s) < d(r_s–1),

r_s–1(x) = r_s(x)q_s+1(x) + 0

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

лева приведена вычислительная процедура последовательного деления многочленов с остатком, называемая алгоритмом Евклида. Вычисления обрываются, как только будет получен нулевой остаток r_s+1(x) = 0. Это обязательно случится, т.к. в противном случае возникает бесконечная убывающая цепочка

d(g) > d(r₀) > d(r₁) > … > d(r_s) > d(r_s+1) > … ,

что невозможно.

Связь алгоритма Евклида с задачей нахождения НОД(f, g) устанавливает следующая

Теорема (Евклида). НОД(f, g) =

Доказательство. Если r₀(x) = 0, т.е. g(x) | f(x), равенство НОД(f, g) = g следует из доказанного в прошлом параграфе свойства 3⁰ наибольшего общего делителя.

Если же r₀(x)  0, т.е. g(x) f(x), то по свойству 4⁰ наибольшего общего делителя последовательно получаем из алгоритма Евклида:

(f, g) = (f(x)–g(x)q₀(x), g(x)) = (r₀ , g) = (r₀(x), g(x)–r₀(x)q₁(x)) = (r₀ , r₁) = … = (r_s–2 , r_s–1) =

= (r_s–2(x)–r_s–1(x)q_s(x), r_s–1(x)) = (r_s , r_s–1) = r_s(x).

Теорема доказана.

Примеры: 1. Найти НОД(x⁶ + 2x² – 3, x² – 1).

Таким образом, НОД(x⁶ + 2x² – 3, x² – 1) = x² – 1.

2. Найти НОД(x² + 2x – 3, x⁴ – 3x³ + x² + 1).

Для того, чтобы применить алгоритм Евклида, вначале переставим местами многочлены: НОД(x² + 2x – 3, x⁴ – 3x³ + x² + 1) = НОД(x⁴ – 3x³ + x² +1, x² + 2x – 3).

Таким образом, НОД(x⁴ – 3x³ + x² +1, x² + 2x – 3) = = –28x + 28 = –28(x – 1). Учитывая, что наибольший общий делитель многочленов определён с точностью до пропорциональности, можно записать проще:

НОД(x⁴ – 3x³ + x² +1, x² + 2x – 3) = x – 1.

3. НОД(x² – 1, x⁴ – 3x³ + x² + 1, x + 1) = (?!) = НОД(x² – 1, НОД( x⁴–3x³+x²+1, x+1)).

П

_ x⁴ – 3x³ + x²+ 1 | x + 1

x⁴ + x³ x³ – 4x² + 5x – 5

_{_} _ –4x³ + x² + 1

–4

x³ – 4x²

_ 5x² + 1

5x² + 5x

_ –5x + 1

–5x – 5

6

ри нахождении НОД( x⁴–3x³+x²+1, x+1) получен остаток 6, на который в последующем делении многочлен x + 1, очевидно, разделится нацело. Поэтому для экономии времени это деление не производим. Значит, НОД(x⁴–3x³+x²+1, x+1) = 1, и искомый наибольший общий делитель равен НОД(x²–1, 1) = 1.

Попробуйте получить этот результат, используя формулу НОД(f, g, h) = НОД(НОД(f, g), h) и почувствуйте разницу.

Упражнения: 1. Найдите НОД(x³ + 1, x² – 1), НОД(x⁴ + 1, x²), НОД(x⁴ + 1, x³ – 1).

2. Докажите, что НОД(fh, gh) = НОД(f, g)h.

3. Верно ли, что НОД(f ², g ²) = НОД(f, g)² ?

4. Чему равен НОД(x²⁰⁰⁷ – 1, x²²³ – 1) ?

5. Докажите, что НОД( + 1, + 1) = 1 при k  m.