Лекции по дискретной математике, страница 4

Теперь можно доказать следующую теорему.

Теорема 2.2.5. Пусть М = П^k_i-1 m_i — произведение попарно взаимно простых положительных целых чисел, пусть М_i = М/ m_i,, и пусть N_i, удовлетворяют равенству N_i M_i +n_im_i=1.Тогда единственным решением системы сравнений

c_i = с (mod т_i;), i=1,2, ,k , будет]

_k

c = ∑ N_i M_i c_i (mod M),

ⁱ⁼¹

Доказательство. Поскольку мы уже знаем, что решение рас­сматриваемой системы сравнений единственно, надо только дока­зать, что выписанное выше с действительно является решением. Но

_k

c = ∑ N_i M_i c_i (mod m_i)= N_i M_i c_i (mod m_i),

ⁱ⁼¹

ибо m_i делит М_r при r≠i. Наконец, так как N_i M_i +n_im_i=1.то N_i M_i =1(mod m_i) и c_i = с (mod т_i;), i=1,2, ,k , что и завершает доказа­тельство.

2.3. КОЛЬЦА МНОГОЧЛЕНОВ

Многочленом над полем GF(q) называется математическое выра­жение

f(x)= f_n-1 x^n-1+f_n-2 x^n-2 +…+f₁ x¹ +f₀ ,

где символ x; называется неопределенной переменной, коэффициенты f_n-1, . .., fо принадлежат полю GF(q), а индексы и показатели сте­пеней являются целыми числами. Нулевым многочленом назы­вается многочлен f(x)=0. Приведенным многочленом называется многочлен, старший коэффициент /_п-1 которого равен 1. Два мно­гочлена равны, если равны все их коэффициенты f_i.

Степенью ненулевого многочлена f (х) называется индекс старшего коэффициента f_n-1; степень многочлена / (х) обозначается через degf(x). Степень ненулевого многочлена всегда конечна. Степень^ нулевого многочлена по соглашению полагается равной отрицательной бесконечности (-∞) .

Множество всех многочленов над полем GF(q) образует кольцо относительно сложения и умножения, определяемых по обычным правилам сложения и умножения многочленов. Такое полиномиальное кольцо можно определить для каждого поля Галуа GF(q). Это кольцо обозначается через GF(q)(x). В исследованиях по кольцам GF(q)(x) элементы поля GF(q) иногда называются скалярами.

Суммой двух многочленов f (х) и g (х) из GF(q)(x) называется многочлен из GF(q)(x),, определяемый равенством

_∞

f(x)+g(x)=∑ (f_i + g_i)xⁱ,

ⁱ⁼⁰

где, конечно, члены с индексом, большим наибольшей из степеней многочленов f(x)и g(x), равны нулю. Степень суммы не превос­ходит наибольшей из этих двух степеней. Например, над GF(2)

(x³ +x² +1) +(x² +x +1)= x³ +(1 +1)x² +x +(1 +1)=x³ +x

Произведением двух многочленов из GF(q)(x) называется многочлен из GF(q)(x), определяемый равенством,

_i

^{f(x)g(x) = ∑}_i^(fj^gi-j^{) x}

. Например, над GF(2) x³ +x² +1) +(x² +x +1)= x⁵ +x +1.

Степень произведения равна сумме степеней множителей.

Кольцо многочленов во многих отношениях аналогично кольцу целых чисел. Чтобы сделать эту аналогию очевидной, в изложе­нии данного параграфа мы следуем § 2.1. Скажем, что многочлен s(x) делится на многочлен r(x) или что r (х) делит s (х), если су­ществует многочлен а(х), такой, что r (х) а (х) = s (х). Многочлен p (х), делящийся только на многочлены ар (х) или a, где а- про­извольный ненулевой элемент поля GF(q), называется неприводи­мым многочленом.Приведенный неприводимый многочлен назы­вается простым многочленом.

Наибольший общий делитель двух многочленов r (x) и s(x) обо­значается через НОД [r (х), s (х) ] и определяется как приведенный многочлен наибольшей степени, делящий одновременно оба из них. Наименьшее общее кратное двух многочленов r (х) и s (х) обозна­чается через НОК [r (х), s (х) \ и определяется как приведенный многочлен наименьшей степени, делящийся на оба из них. Как мы увидим, наибольший общий делитель и наименьшее общее кратное определены единственным образом, так что наше определение кор­ректно. Если наибольший общий делитель двух многочленов ра­вен 1, то они называются взаимно простыми.

Если r(х) одновременно делится на s(х) и делит s (х), то r (х) = as(x), где а -элемент поля GF(q). Это доказывается следую­щим образом. Должны существовать многочлены а (х) и b (х), та­кие, что r (х) = s (х) а (х) и s (х) = r (х)b (х); следовательно, r (х) = r (x) b (х) а (х). Но степень правой части равна сумме степеней r (х), b (х) и а (х). Так как эта величина должна быть равной степени левой части, то b (х) и а (х) должны иметь нулевую степень и, таким образом, являться скалярами.

Для многочленов над полем вещественных чисел очень полезна (и элементарно вводится) операция дифференцирования. В случае многочленов над конечным полем определение дифференцирова­ния в смысле операции предельного перехода невозможно. Тем не менее удобно определить операцию над многочленами, резуль­тат которой ведет себя так, как вела бы производная. Такой мно­гочлен называется формальной производной от многочлена.

Определение 2.3.1. Пусть r (х) = r_п-1х^п-1 + r_п-2 х^п-² +• • • +r₁x +r₀ —многочлен над GF(q) Формальная производная от r (х) определяется как многочлен вида

r' (х) = ((п - 1))r^n-1 x^n-2 + ((п - 2)) г_n-2_x^n-3 + • • • + r₁ ,

где коэффициенты ((i)) называются числами поля ОР (а) и вычис­ляются как сумма I единиц членов в поле GF(q)

((i)) = 1 + 1 +•••+ 1.

Легко проверить, что сохраняются многие полезные свойства производных, а именно что

﴾r (x) s (x)﴿ ’ = r'(x) s(x) + r(x) s'(X)

и что если а²(х) делит r (х), то а (х) делит r' (х.)

В кольце многочленов, так же как и в кольце целых чисел, деление в общем случае невозможно. Однако для многочленов над полями тоже имеют место сокращение и деление с остатком. Алгоритм деления для многочленов дается следующим утвержде­нием.

Теорема 2.3.2 (алгоритм деления для многочленов). Для каждой пары многочленов с(х) и d(х), d(х)≠0, существует единственная пара многочленов Q(х) (частное) и s(х) (остаток), таких, что

с (х) = Q(х)а (х) + s (х) и deg s(x)< deg d(x)ю

Доказательство. Частное и остаток находятся по элементарному правилу деления многочленов. Они единственны, так как
если

с (х) = d(х) Q₁(х) + s₁(х) = d(х)Q₂(x) + s₂ (х),

то

d(х) (Q2(x) - Q₂(х) ) = s₂ (х) –s₁(х) .

В правой части стоит ненулевой многочлен, степень которого меньше deg d (х), а в левой— ненулевой многочлен, степень которого не меньше deg d (х). Следовательно, оба многочлена равны нулю, и представление единственно.

Практическое вычисление частного и остатка выполняется с помощью простого правила деления многочленов «уголком». Обычно мы будем больше интересоваться не частным, а остатком. Остаток можно также записать в виде s (х) = R_d(х)[с (х)]. Часто остаток называют вычетом многочлена с(х) по модулю многочлена d(х). Несколько отличным понятием является сравнение

s(х)≡с (х) (mod d(х)),

которое означает, что при делении на d (х) многочлены s(х) и c(х) дают один и тот же остаток, но степень многочлена s(х) не обязательно меньше степени многочлена d(х).

Иногда при вычислении остатка удобнее разбивать деление на этапы. Это можно осуществить с помощью следующей теоремы.

Теорема 2.3.3. Пусть d(х) кратен многочлену g(х). Тогда для любого а (х)

R_g(х)[a (х)]= R_g(x)[ R_d(х)[a(х)].

Доказательство. Пусть d(х) = g(х) h(х) для некоторого h(х). Раскрывая правую часть, получаем

a(х) =Q₁ d(х) + R_d(х)[a(х)]= Q₁(х) g(х) h(х) +Q₂(х) g(х) +R_g(x) [R_d(х)[a(х)]},

где степень остатка меньше deg g(x). Раскрывая левую часть, имеем

а(х) = Q₃(х)g(х) + R_g(х)[a (х)],.

и, согласно алгоритму деления, такая запись однозначна при степени остатка, меньшей deg g(x). Теорема вытекает из отождествления подобных членов в обоих выражениях.

Теорема 2.3.4.

(1) R_d(х)[a(х)+b(x)]= R_d(х)[a(х)]+ R_d(х)[b(х)]

, (2 ) R_d(х)[a(х)b(x)]= R_d(х)[ R_d(х)[a(х)] R_d(х)[b(х)].]

Доказательство сводится к упражнению: использовать алгоритм деления для выражений в обеих частях равенства и приравнять остатки.

Подобно тому как часто бывает полезным представление положительных целых чисел в виде произведения простых сомножителей, часто бывает полезным представление приведенных много­
членов в виде произведения простых многочленов.

Теорема 2.3.5 (теорема об однозначном разложении). Ненулевой многочлен p(х) над некоторым полем однозначно (с точностью до порядка следования множителей) разлагается в произведение элемента поля и простых многочленов над этим полем

Доказательство. Ясно, что входящим в произведение элементом поля должен быть коэффициент р_п-1, где п-1 —степень многочлена р (х). Можно пренебречь этим элементом и доказывать теорему для приведенных многочленов.

Предположим, что теорема не верна. Пусть р (х) — приведенный многочлен наименьшей степени, для которого не верна теорема. Тогда имеются два разложения:

р (х) = а₁ (х) а₂ (х) ... а_к(х) = b₁(х) b₂ (х) ... b_l(х),,

где a_i(х) и bi(х) — простые многочлены.