Множества и операции над ними. Отношение принадлежности. Множество. Элемент. Унификация объектов, страница 14

Когда множество ясно из контекста, нижние индексы в записи обычно опускают: [x]={y | xºy}.

Операции над классами вычетов

Определение и обозначение:

[x]+[y]=[x+y]

[x] · [y]=[x·y]

Необходимо проверить, что эти выражения действительно определяют бинарные операции на A/º = {[x] | xÎA} - фактормножестве (множестве всех различных классов эквивалентности). Именно, что введенные обозначения не зависят от выбора порождающих элементов:

[x]=[x¢], [y]=[y¢] Þ

Þ xºx¢, yºy¢ Þ x-x¢ÎI, y-y¢ÎI Þ

1)  (x+y)-(x¢+y¢)=(x-x¢)+(y-y¢)ÎI Þ x+yºx¢+y¢ Þ [x+y]=[x¢+y¢]

2)  x·y - x¢·y¢ = x·y - x¢·y + x¢·y - x¢·y¢ = (x-x¢)·y + x¢·(y-y¢) ÎI Þ x·yºx¢·y¢ Þ [x·y]=[x¢·y¢]

Факторкольца (кольца классов вычетов)

Фактормножество A/º = {[x] | xÎA} вместе с введенными операциями + и · на нем называется факторкольцом  или кольцом классов вычетов <A/º,+,·>.

Элемент [0] играет роль нейтрального элемента первой операции, а элемент [1] - второй.

Элемент [-x] является обратным для [x]. Алгебра <A/º,+,·> обладает всеми свойствами кольца.

Если взять в качестве алгебры <A,+,·> кольцо целых чисел с операциями сложения и умножения <Z,+,·>, а в качестве идеала I множество чисел, кратных некоторому числу p (I={n·p | nÎZ}), то получится кольцо классов вычетов по модулю числа p, в котором каждый класс может быть представлен числом от 0 до p-1. Для него предусмотрено обозначение Z/p.

Вычисления в этой алгебре заключаются в сложении или умножении порождающих элементов и вычислении остатков от деления на p.

Поля простого порядка

Если p - простое число, то кольцо классов вычетов по модулю числа p будет областью целостности, так как 0<a,b<pÞ a·b¹n·p.

Так как число классов вычетов конечно, то эта алгебра будет также и полем:

pÎP Þ Z/p -поле.

3. Конечные поля.

Характеристика поля

Число p = min m: ^m1=0 называется характеристикой поля (порядок элемента 1 по операции +).

Характеристика поля - простое число.

Доказательство:

Если характеристика поля p -составное, то p=p₁p₂,  p₁,p₂<p   Þ Þ , что противоречит определению характеристики. Поэтому p - простое число.

Такой же порядок по операции + имеют все элементы из A\{0}

Подполе простого порядка

В каждом конечном поле содержится подполе простого порядка.

Множество элементов {^k1|kÎN} образует подполе (замкнутость по + и ×, наличие элементов 0=^p1 и 1=¹1). Оно изоморфно Z/p:

Взаимно однозначное соответствие для kÎ1..p-1

f(k)=^k1.

Сохранение операций:

f(x+y mod p)=f(x)+f(y)=^x1+^y1=^{x+y mod p}1

f(xy mod p)=f(x)×f(y)=^x1× ^y1=^{xy mod p}1

Векторное представление элементов

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

<A,+,×> - конечное поле, <B,+,×> - некоторое подполе (обычно <{^k1|kÎN},+,×>, так как эта алгебра всегда будет подполем).

Шаг 1. Взять любой элемент x₁ из A\{0}. Построить множество А₁={a₁×x₁|a₁ÎB}.

Если А₁=A (и =B) то построение закончено - поле имело простой порядок - x₁ будет базисным элементом. Иначе перейти к шагу 2.

Шаг 2. Взять любой элемент x₂ из A\A₁. Построить множество A₂={a₁×x₁+a₂×x₂|a₁,a₂ÎB}. A_1ÌA₂, x_2ÏA₁ x_2ÎA₂, так что число элементов может только увеличиться. Если A₂=A, то построение закончится на этом шаге, x₁,x₂-базисные вектора. Иначе аналогично поступают с A\A₂.

В результате на некотором шаге m из-за исчерпания элементов в конечном множестве A будет получено следующее представление:

A=A_m={a₁×x₁+a₂×x₂+…+a_m×x_m|a_iÎB}

¨  Упражнение

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

2.  Построить поле из четырех элементов, используя однозначность построения с учетом определений при выбранных 0 и 1, и получить векторное представление описанным способом через подполе с элементами 1 и 1+1=0.

3.  Доказать, что число элементов в конечном поле может быть только степенью простого числа.