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

(a+bp) = а * (modp ). Тогда для некоторого целого k

(а + ад- -=

Возведем это выражение в р-ю степень:

(а + Ьр) = 0 + pkp a

Второй член справа, так же как и все члены суммы, делится на pm+i. следовательно,

(а + ад * ЕЕ а- (modp-n

так что утверждение справедливо при переходе от m к от + 1, что и завершает индукцию.

Шаг I. Положим в утверждении шага О числа а и 6 равными 1. Тогда

(1 + р) = 1 (modp ),

так что порядок элемента (1 + р) делит р -. Покажем теперь, что при нечетном р порядок этого элемента в точности равен р * , для чего докажем, что этот порядок не делит числа р ~. А именно, для завершения доказательства шага i докажем, что если т > 1, то

= 1-

(mod р ).

Непосредственно проверяется справедливость утверждения для от = 2. Предположим, что оно выполняется для некоторого т. Тогда для некоторого к выполняется равенство

(i+pf -l + p +кр .

Следовательно,

(1 + рГ = 1 + р (р - + крП + 2(0 (/> + +

Если р нечеггно, то каждое из чисел j- ..... р--1)

лится на р. Каждый член в сумме делится по меньшей мере на р2 (m-i)+i и, следовательно, делится на р + при ш > 2. По- !

следний член в правой части равенства делится на рР(-и, следовательно, при р > 3 и от > 2 делится на р +>. (Заметим, что доказательство не проходит при р = 2.) Следовательно, порядок элемента (1 + р) (mod р ) не делит р-. Это завершает доказательство того, что порядок элемента (1 + р) равен р .

Шаг 2. Так как группа Gm содержит р - (р - 1) элементов, то порядок каждого ее элемента делит р - (р - 1). Чтобы найти элемент группы порядка (р - 1) (mod р ). выберем л равным примитивному элементу кольца z/(p). Тогда порядок л равен (р - 1) (modp). Покажем, что а = п представляет собой искомый элемент порядка (р - 1) (mod р ). Так как л = = 1, то порядок элемента а должен делить р - 1; поэтому надо только показать, что порядок элемента а не меньше, чем р - 1.

Так как к примитивенв кольце z/(p), то р - 1 степеней л для / = О, .... р - 2, могут быть записаны в виде целых чисел л = fli + feiP, где ui пробегает все различные ненулевые целые числа, не превосходящие р - 1. Следовательно, используя шаг О, имеем

(я) : = {а. + hpf- = af- (mod р ),

=af (modp ), где Ol пробегает все различные ненулевые целые числа, не превосходящие р - 1. Следовательно, если мы докажем, что для любых двух целых чисел а и 6, не превосходящих р - 1, выполняется соотношение

а V 6°* (modp ), то отсюда следует, что порядок элемента а больше, чем р - 2.

Но а = а для любого элемента кольца 2/(р), так что а = = о (mod р). Следовательно, если

рт-1

ТО, конечно,

(mod р ), (mod р).

и, таким образом,

а = Ь (mod р),

что противоречит предположению о том, что а и ft различные не превосходящие р - 1 целые числа. Следовательно, порядок элемента а равен р - 1 и п. (i) теоремы доказан.

Шаг 3. Порядок каждого элемента группы G, делит 2 -. Чтобы доказать это, сначала докажем, что для любых целых а и ft выполняется сравнение

(mod 2 ).

ia + Abf - = а

Поскольку элементами группы являются только нечетные числа, то, полагая а = ± 1 и варьируя Ь, сразу получаем из этого сравнения нужное утверждение. п m - 9 оно ппове-

Соавнение доказывается индукцией. Для m ~ 2 оно прове ряеГся непосредственно. Предположим, что оно справедливо для Soporo положительного целого т. Тогда для некоторого целого к

(a+4i)-

21-2 2 2

и, следовательно. Таким образом,

(a+ibf ~=a (mod2 +)-Шаг 4. Нам осталось найти элемент порядка 2 - при m > 3. Покажем, что 3° # 1 (mod 2 ), так что 3 должно быть эле-мектбм порядка 2 -2. При m = 3 это утверждение проверяется непосредственно. Доказательство утверждения при /п > 4 со-состоит в доказательстве сравнения

(l+2f= 1 + 2- (mod2 ). Это сравнение просто проверяется для /я = 4. Предположим, что оно справедливо для некоторого m > 4. Тогда для некоторого к

Следовательно,

(14 2Г = 1 + 2 *+*2 .

(1 + 2Г-=(1+2 *-+*2 ) =

-ft2

и, таким образом, так как т больше трех,

(1+2Г = l+2 (шod2 +) Cлeдoвaтeльнo, при всех m > 3 выполняется сравнение

(1+2) = 1+2 - (mod г ). Таким образом, порядок 3 (mod 2 ) не делит г - и, следова. тельно, он равен 2 , что и завершает доказательство. D

5.2. Конечные поля, основанные на кольце целых чисел

Имеется очень важная конструкция, позволяющая по заданному кольцу построить новое кольцо, называемое его фактор-кольцом. В случае произвольного кольца построение его фактор-

кольца опирается на смежные классы. В случае кольца целых чисел факторкольцо строится просто: оно представляет собой кольцо целых чисел по модулю q, с которым мы уже встречались ранее, и обозначается через zl(q) (или, более кратко, z,); в этом случае его. называют кольцом вычетов.

Пусть q - положительное целое число. Кольцом вычетов

Zl{q) называется множество 0, 1.....q-Ц с операциями

сложения и умножения, определяемыми равенствами а + & =

= 1о + 1. а* = Кя

Элементы, обозначенные через {О, 1, q-1[, принадлежат как Z, так и z/(i7). Элементы кольца zl(q) названы так же, как и первые q элементов кольца 2. Дело вкуса, подразумевать ли под ними те же самые математические объекты или некоторые другие объекты с теми же именами.

Два элемента а и 6 кольца z, отображаемые в один и тот же элемент кольца Zl(q), называются сравнимыми по модулю!;, и а = 6 + mij для некоторого целого т.

Теорема 5.2.1. Кольцо вычетов z/iq) является кольцом.

Доказателвство. Непосредственная проверка выполнения свойств кольца. D

. Теорема 5.2.2. Ненулевой элемент s кольца zl(q) обратим относительно умножения тогда и только тогда, когда s uq взаимно просты.

Доказательство. Пусть s - такой ненулевой элемент кольца, что S и <; взаимно просты. Тогда согласно следствию 2.6.4 найдутся целые числа а и Ь, такие, что 1 = а? + bs. По модулю д соответственно имеем

1 = [1] = Я, И + 6sl = Л, [ад] + [bs]) =

= R, lbs] = {R, [b] R, Is]] = Rg{Rglb]-s\.

Следовательно, относительно умножения no модулю g мультипликативный обратный к S равен R lb].

Пусть теперь s такой элемент кольца, что s и ? не взаимно просты. Сначала рассмотрим случай, когда s делит q: q = s-r. Пусть у элемента s есть обратный s . Тогда

г = = K,ls--s-r] = R,ls--q] = 0.

Но г :5b О (mod 17), так что получаем противоречие. Таким образом, если S является делителем q, то он не имеет обратного.

Теперь рассмотрим случай, когда s и 17 не взаимно просты, но S не делит д. Пусть d = НОД Is, д]. Тогда s = ds для некоторого s, взаимно простого с 17, и делителя d числа д. Если элемент S обратим, то и элемент d также обратим: d = sV, что

противоречит только что доказанному утверждению. Следовательно, S не может быть обратимым, и теорема доказана. □

Поскольку обращение в кольце zl(q) возможно не всегда, то в общем случае ненулевые элементы кольца zl(q) группы по умножению не образуют. Однако в zl(q) можно найти подмножества, образующие подгруппы. Выберем в кольце zl(q) ненулевой элемент (i и сформируем подмножество Р, Р , = Ц, остановив процесс, как только получим единичный элемент. Мы уже видели, что единичный элемент всегда достижим и что конструкция приводит к циклической группе. Она является подгруппой кольца zliq), и целое число г называется порядком элемента р в zl(q).

Мы уже видели в примерах разд. 2.3, что арифметика полей GF (2) и GF (3) может быть задана как сложение и умножение по модулю 2 и 3 соответственно, но арифметика поля GF (4) так описана уже быть не может. В символической записи GF (2) = = Z/(2), GF (3) = z/(3), GF (4) ф z/{i). Общий результат описывается следующей теоремой.

Теорема 5.2.3. Кольцо вычетов zl(q) является полем тогда-и только тогда, когда q равно простому числу.

Доказательство. Предположим, что q просто. Тогда каждый элемент кольца zl{q) взаимно прост с q я, следовательно (по теореме 5.2.2), обратим относительно умножения.

Предположим теперь, что i; составное число. Тогда q = r-s и согласно теореме 5.2.2, г и s не могут иметь обратных элементов. □

Если кольцо вычетов Z/(g) является полем, то чтобы подчеркнуть этот факт, оно обозначается через GF (q). Конечные поля, построенные как кольца вычетов целых чисел, не исчерпывают всего множества полей, но конечные поля с простым числом элементов всегда могут быть построены как кольца вычетов.

Если поле GF (р) не содержит квадратного корня из -I, то его можно расширить до GF (р) точно таким же способом, как поле вещественных чисел расширяется до поля комплексных чисел. Например, в поле GF (7) выполняется равенство 6 = -1, но, как легко проверить, поле не содержит элемента, квадрат которого равен 6. Следовательно, поле GF (49) можно задать : множеством элементов вида

GF(Щ = [а + lb : а, bGF(!)], определив на нем операции сложения и умножения так же, как для комплексных чисел:

(а + jb) -f (с + id) = (а + с) + j(b + d), (а + jb) (с + jd) = (ас - bd) + ; {ab + cd),

Р = (1 -I- I + ... -Ц) р = р

+... -ь

где сумма содержит а копий элемента р и сложение выполняется как сложение по модулю р. Следовательно, умножение также является умножением по модулю р. Относительно умножения каждый ненулевой элемент р имеет обратный, так как последовательность р, 2р, Зр, ... образует в G циклическую подгруппу. Поскольку а-Р#0 для любых ненулевых а и р из исходного поля, то аР О по модулю р для всех целых поля, и, следовательно, р должно быть простым. Таким образом, подмножество G образует в точности простое поле, описываемое теоремой 5.2.3.

Альтернативным является случай, когда множество G бесконечно. В этом случае оно изоморфно кольцу целых чисел. Наименьшее содержащее G подполе F изоморфно наименьшему полю, содержащему кольцо целых чисел, каковым является поле рациональных чисел. □

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

где во всех скобках справа операции обозначают сложение и умножение в поле GF (7). При таком определении множество GF (49) является полем. Целыми поля GF (49) являются элементы поля GF (7), так что. характеристика поля GF (49) равна 7.

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

Доказательство. Каждое поле содержит О и 1. Для построения подполя рассмотрим подмножество G = 0, I, 1 -j- 1, 1 -f 1 + -f 1, ... I, обозначая его элементы соответственно 0, 1, 2, 3, .... Это подмножество содержит либо бесконечное множество элементов, либо конечное множество, скажем р. Мы покажем, что если это число конечно, то оно просто и G = GF (р). Так как G является циклической группой, то сложением в нем служит сложение по модулю р. В силу наличия в поле дистрибутивного закона умножение в G также является умножением по модулю р, так как