Краткий план. Введение в алгебру полиномов. Наибольшие общие делители полиномов над полем (стр. 6 из 8)

Следствие. Для

имеет место равенство:

.

Теорема. Пусть

и - два нормированных полинома над GF(p), такие что

, .

Тогда

Доказательство: Из предположения следует, что

. Поэтому

Помимо этого

для , и полиномы и также взаимно просты. Поэтому .

Таким образом, пусть

- свободный от квадратов полином степени n, который нужно разложить на множители над GF(p), и предположим, удалось найти полиномы , , такие что . По одной из ранее доказанных теорем, полином имеет в ровно p корней. А именно 0,1…p-1. Значит он раскладывается следующим образом . Заменив х на , в кольце получим . Так как , то . Кроме того поскольку полиномы и - взаимно простые при , то - нетривиальное разложение полинома над GF(p).

Теперь задача состоит в определении полиномов

. Это можно осуществить с помощью решения систем линейных уравнений, получаемой следующим образом. Пусть

, где коэффициенты требуется найти. Нужно сначала проверить делит ли полином . Ранее доказано, что .

Разделив

на получаем , где . Теперь, заменив на соответствующие выражения, получим

+[кратное ].

Таким образом

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

Пусть

- матрица, строки которой образуют

коэффициенты полиномов остатков. По этому всему имеет место

Теорема. Полином

является решением сравнения тогда и только тогда, когда .

Пусть N – множество векторов

, таких что называется нуль-пространством матрицы . У этого пространства имеется базис и размерность.

Теорема. Число различных неприводимых сомножителей

полинома в равно размерности нуль-пространства матрицы .

Доказательство: Полином

тогда и только тогда когда каждый , . По ранее доказанным фактам для набора существует единственный , такой что . Существует решений сравнения . является решением сравнения если . Для вопроса о неприводимости получен

Тест3. Полином

степени n>1 неприводим в тогда и только тогда когда нуль-пространство матрицы одномерно и .

Доказательство: Нуль-пространство матрицы

одномерно тогда и только тогда когда - степень неприводимого полинома. Тогда берём r(x)=1.

Теорема. Пусть

в и - базис нуль-пространства. Тогда для каждого , , существует k и , такие что делит, а не делит .

Доказательство: В нуль-пространстве существует вектор,

-ая компонента которой отлична от -ой. Значит найдётся такое k, , . Положим .