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

Лемма 1. Пусть f(x) M g(x) , тогда (f(x), g(x)) = g(x).

Лемма 2. Пусть f(x) = g(x)⋅q(x)+r(x), тогда (f(x), g(x)) = (g(x), r(x)).

Алгоритм Евклида заключается в следующем.

Делим вначале f(x) на g(x) с остатком. Получим равенство

f(x) = g(x)⋅q1(x)+r1(x),

где либо r1(x) = 0, либо степень r1(x)меньше степени g(x). Если r1(x) ≠ 0, то

далее делим g(x) на r1(x) с остатком. Получим

g(x) = r1(x)⋅q2(x)+r2(x),

где r2(x) = 0 либо степень r2(x) меньше степени r1(x).

При r2(x) ≠ 0 делим r1(x).на r2(x) с остатком

r1(x) = r2(x)⋅q3(x)+r3(x)

10

Здесь либо r3(x) = 0, либо степень r3(x) меньше степени r2(x). И т.д.

В процессе последовательного деления степени получаемых остатков

r1(x), r2(x), r3(x),... убывают, оставаясь целыми неотрицательными числами.

Поэтому этот процесс не может продолжаться бесконечно, т.е. на каком-то s-

ом шаге мы получим в остатке rs(x), который далее разделит rs-1(x) без

остатка. Покажем, что rs(x) = (f(x), g(x)).Для этого запишем весь процесс

последовательного деления в виде системы равенств:

f(x) = g(x)⋅q1(x)+r1(x);

g(x) = r1(x)⋅q2(x)+r2(x);

r1(x) = r2(x)⋅q3(x)+r3(x); (5)

... ... ... ... ... ... ... ...;

rs-2(x) = rs-1(x)⋅qs(x)+rs(x);

rs(x) = rs(x)⋅qs-1(x).

По лемме 2. из 1-го, 2-го и т.д. равенств системы (3.8) соответственно

получим

(f(x), g(x)) = (g(x),r1(x))

(g(x), r1(x)) = (r1(x), r2(x))

(r1(x), r2(x)) = (r2(x), r3(x)) (6)

... ... ... ... ... ... ... ...

(rs-2(x), rs-1(x)) = (rs-1(x), rs(x))

Наконец по лемме 3.1 из последнего равенства системы (3.8) следует

(rs-1(x), rs(x)) =rs(x) (7)

Теперь из (6) и (7) непосредственно вытекает, что

(f(x), g(x)) = rs(x).

Описанный процесс последовательного деления и называется

алгоритмом Евклида. Таким образом, нами доказано, что (f(x), g(x))

существует и равен последнему остатку, отличному от нуля, алгоритма

Евклида, примененного к многочленам f(x) и g(x). Очевидно, что (f(x),

g(x))∈P[x].

8. Свойства линейности НОД

Теорема 3.3. (свойство линейности НОД многочленов). Пусть

d(x) = (f(x),g(x)), тогда существуют такие многочлены ϕ(x) и ψ(x) в кольце

P[x], что

f(x)⋅ϕ(x)+g(x)⋅ψ (x) = d(x). (8)

9. Взаимно простые многочлены

Определение 3.3. Многочлены f(x) и g(x) называются взаимно

простыми, если их наибольший общий делитель является многочленом

нулевой степени, то есть числом из поля Р, отличным от нуля. При этом

пишут (f(x), g(x)) = 1.

Теорема 3.4. Многочлены f(x) и g(x) тогда и только тогда взаимно

просты, когда в кольце P[x] найдутся такие многочлены ϕ(х) и ψ(х), что

f(x) ϕ(х)+g(x) ψ(х) = 1

10. свойства взаимно простых многочленов.

Свойство 1. Пусть h(x)|f(x)⋅g(x), причем (h(x), f(x)) = 1. Тогда

h(x)|g(x).

Свойство 2. Пусть (f(x), g(x)) = 1. Многочлен h(x) тогда и только тогда

делится на произведение f(x)⋅g(x), когда h(x)M f(x) и h(x)M g(x).

Свойство 3. Пусть многочлен g(x) взаимно прост с каждым из

многочленов f1(x), f2(x), ..., fk(x). Тогда g(x) взаимно прост и с произведением

этих многочленов.

11. Неприводимые многочлены над полем

Определение 4.1. Многочлен f(x) из кольца P[x] степени n≥1

называется неприводимым над полем P, если он не имеет других делителей,

кроме многочленов нулевой степени и многочленов, ассоциированных с f(x).

Если же многочлен f(x) кроме указанных имеет и другие делители из кольца

P[x], то его называют приводимым над полем P.

Очевидно, что многочлен f(x) тогда и только тогда приводим над

полем P, когда его можно представить в виде произведения f(x) = f1(x)⋅f2(x),

где f1 и f2 – многочлены из кольца P[x], степень каждого из которых меньше

степени многочлена f(x).

Пример 4.1. Многочлен f(x) = x2–2 неприводим над полем Q

рациональных чисел.

Свойство 1. Пусть р(х) – многочлен неприводимый над полем Р, тогда

всякий многочлен ассоциированный с р(х) также неприводим над Р.

Свойство 2. Пусть р(х) неприводим над полем Р и f(x) – произвольный

многочлен из кольца P[x]. тогда либо p(x) | f(x) либо (f, p) = 1.

Свойство 3. Пусть р(х) и q(x) неприводимы над полем Р и p(x) M q(x) ,

тогда р(х) и q(x) ассоциированы.

Свойство 4. Пусть неприводимый многочлен делит произведение

многочленов f1(x)⋅f2(x) …fn(x), тогда р(х) делит хотя бы один из

сомножителей этого произведения.