Наибольший общий делитель многочленов. Алгоритм Евклида.

Теорема. Для любых f эF[x] и g эF[x], одновременно не равных нулю, их наибольший общий делитель d существует и определен однозначно с точностью до множителя c, где c — произвольная ненулевая константа.

Доказательство. Вначале докажем, что если НОД существует, то он определен с точностью до множителя c. Действительно, если d, d₁ — наибольшие общие делители многочленов f и g, то d:d₁ и d₁:d, поэтому по пункту имеем d = cd1 для некоторой константы c.
Приведем конструктивное доказательство существования наибольшего общего делителя. Опишем хорошо известный алгоритм Евклида нахождения НОД. Если f <> 0, а g = 0, то, очевидно, в качестве наибольшего общего делителя можно взять f, поэтому, не нарушая общности, можно считать, что  g <> 0 (напомним, что f и g не равны нулю одновременно). На нулевой итерации разделим f на g, в частном получим q1, в остатке — r₁. Если r₁ <>0, то перейдем к первой итерации, на которой разделим g на r₁, в частном получим q₂, в остатке — r₂. На i-й итерации разделим r_i−1 на r_i , в в частном получим  q_i+1, в остатке— r_i+1. Вычисления продолжаются до тех пор, пока на некоторой, скажем, s-й, итерации вычисленный в результате очередного деления остаток r_s+1 не будет нулевым. Докажем, что r_s является наибольшим общим делителем многочленов f и g. Имеем

f = q₁g + r₁, (β0)

g = q₂r₁ + r₂, (β1)

r₁ = q₃r₂ + r₃, (β2)

r_s−3 = q_s−1r_s−2 + r_s−1, (βs−2)

r_s−2 = q_sr_s−1 + r_s, (βs−1)

r_s−1 = q_s+1r_s. (βs)

Из равенства (β_s) следует, что (r_s−1):r(s). Поэтому в правой части равенства (β_s−1) первое слагаемое делится на r_s. Так как второе слагаемое, очевидно, также делится на r_s, то вся правая часть равенства (β_s−1) делится на rs, поэтому на rs делится и левая часть этогоьравенства, т. е. r_s−2. В правой части равенства (β_s−2) на rs также делятся оба слагаемых

и, следовательно, (r_s−2): r_s. Рассматривая эти равенства далее снизу вверх (легко провести

индукцию), приходим к выводу, что на rs делятся правые части в (β₀) и (β₁), т. е. f:r_s и

g:r_s, т. е. r_s — общий делитель многочленов f и g.

Теперь покажем, что любой общий делитель d многочленов f и g является также делителем многочлена r_s. Так как f:d и g:d, то из (β₀) получаем, что r₁:d. Далее, так как g: d

и r₁:d, то из (β₁) получаем, что r₂: d. Рассматривая далее эти равенства сверху вниз (легко

провести индукцию), приходим к выводу, что r_s:d.

Итак, НОД двух ненулевых многочленов существует и определен с точностью до постоянного множителя. Чтобы избежать многозначности, среди всех возможных НОД двух многочленов f, g можно выбрать многочлен со старшим коэффициентом 1 (если это не так, то разделим многочлен на старший коэффициент). Именно его мы будем обозначать НОД(f, g).

 

Расширенный алгоритм Евклида для многочленов. Коэффициенты Безу (линейное разложение НОД).

Пусть f, g, d — ненулевые многочлены из F[x] и d — НОД многочленов f и g. Тогда найдутся такие u, v из F[x], что       uf + vg = d, причем deg u < deg g, а deg v < deg f. Многочлены u и v называются коэффициентами Безу.

Доказательство. Очевидно, что достаточно научиться находить коэффициенты Безу по крайней мере для одного из возможных НОД, например, для НОД, выдаваемого алгоритмом Евклида. Применим к f и g алгоритм Евклида. В ходе его работы получим последовательности частных q₁, q₂, . . . , q_s+1 и остатков r₁, r₂, . . . , r_s. На первой итерации запишем два тривиальных равенства:

f = 1 · f + 0 · g, (γ−1)

g = 0 · f + 1 · g, (γ0)

и вычтем из первого второе, умноженное на q₁. Тогда согласно (β₀) в левой части получим r₁. В правой части соберем множители у f и у g:

r₁ = 1 · f + (−q₁) · g. (γ1)

На второй итерации вычтем из равенства (γ0) равенство (γ1), умноженное на q₂. Согласно (β₁) в левой части получим r₂. В правой части снова соберем множители у f и у g:

r₂ = (−q₂) · f + (1 + q₁q₂) · g. (γ2)

На третьей итерации из (γ1) вычтем (γ2), умноженное на q₃. Согласно (β₂) в левой част получим r₃. В правой части снова соберем множители у f и у g:

r₃ = (1 + q₂q₃) · f + (−q₁ − q₃ − q₁q₂q₃) · g. (γ3)

Будем выполнять такие преобразования далее. На k-й итерации (k = 1, 2, . . . , s), вычитая из равенства (γk−2) равенство (γk−1), умноженное на q_k, получим

r_k = u_kf + v_kg, (γk)

где u_k, v_k — некоторые многочлены. На s-й итерации получим

d = r_s = u_sf + v_sg. (γs)

Можно считать, что многочлены us и vs ненулевые . Если    deg u_s < deg g и deg v_s < deg f, то u_s и v_s — искомые коэффициенты Безу. В противном случае выполним следующую процедуру.

Пусть, для определенности, deg u_s ≥ deg g. Разделим u_s на g: u_s = qg + r. Теперь из (γs)

получаем

d = rf + (v_s + qf)g.

Обозначим u = r, v = v_s + qf. Имеем uf + vg = d и deg u < deg g. Покажем, что deg v < deg f,

тем самым завершив доказательство теоремы. Предположим противное: deg v ≥ deg f, тогда

deg(uf) < deg g + deg f, но deg(vg) ≥ deg g + deg f, поэтому

deg d = deg(uf + vg) ≥ deg g + deg f,

что противоречит тому, что d — НОД многочленов f и g.

Алгоритм нахождения коэффициентов Безу, описанный при доказательстве теоремы, называется расширенным алгоритмом Евклида

⇐ Предыдущая1234567Следующая ⇒

Поделиться: