А5. Алгебра по модулю 2

Не следует смешивать алгебру по модулю 2 с двухэлементной булевой алгеброй, хотя обе они связаны с множеством (

Отличие их состоит в том, что

Сравним эти алгебры В двухэлементной булевой алгебре если то и если то в алгебре по модулю 2 если то если то Имеем

Далее,

Следовательно, чтобы перейти от формулы в двухэлементной булевой алгебре к формуле в алгебре по модулю 2 и обратно,

достаточно выразить операции и друг через друга, используя формулы

Заметим, что операция есть не что иное, как операция (дизъюнктивная сумма), хорошо известная в булевой алгебре:

Следовательно, можно не различать символы

Переход от булевых формул к формулам по модулю 2 не всегда прост:

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

Алгебра полиномов в Z/2. Лемма. Пусть

— полином степени где с коэффициентами из Существует такое поле К, содержащее что все корни принадлежат К.

Если а — корень полинома

то

Выразим через

Следовательно, все степени а линейно выражаются через первые степеней

Так как таких функций самое большее то и число различных степеней а не превосходит Последовательность этих степеней периодическая с периодом

т. е.

Действительно, так как среди первых степеней по крайней мере две совпадают, то существуют такие что т. е.

Пусть наименьшее число, для которого Тогда где остаток от деления на

Корни периодически повторяются (с периодом

Обозначим через корни Так как они содержатся среди различных степеней а, то

Рассмотрим полином

Его можно представить в виде

или

где полином с коэффициентами из К.

Более того, из следует, что коэффициенты принадлежат Теперь мы в состоянии сформулировать основную теорему Галуа.

Теорема Галуа. Для любого полинома степени найдутся такой полином и число что

Рассмотрим несколько свойств.

1) Если таков, что то говорят, что примитивный полином, дополнительный к

2) Примитивный полином неприводим.

3) Корень примитивного полинома степени называют примитивным элементом; остальными корнями будут

4) Все корни примитивного полинома различны. Пример. Пусть

и а — его корень. Все различные степени

Имеем

Полином также примитивный, так как