logo
Рожков_Ниссенбаум_ТЧМК_лекции

3.5. Алгебраические структуры на целых числах.

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

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

Группой называют множество G с заданной на нем бинарной операцией •, если:

а) Операция • ассоциативна, то есть a,b,c G выполняется (a•b)•c=a•(b•c);

б) a•e=e•a=a (Если групповая операция называется сложением, то e называют нулевым элементом, если операция – умножение, то e называют единичным элементом.);

в) (Если групповая операция называется сложением, тоx´ называют противоположным к x элементом, если операция – умножение, то обратным элементом.);

Если операция группы <G,•> коммутативна (то есть ), то группа называетсякоммутативной, или абелевой.

Утверждение 1

< Zm , +(mod m)> — абелева группа.

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

Докажем, что Zm вместе с операцией сложения по модулю m образуют абелеву группу. Действительно, операция сложения не выводит за пределы множества целых чисел, а Zm покрывает своими вычетами всё Z, поэтому можно сказать, что операция +(mod m) задана на Zm. Ассоциативность операции +(mod m) следует из ассоциативности сложения, в качестве нулевого элемента выступает «0», а в качестве противоположного к a выступает m—a. Коммутативность групповой операции следует из коммутативности сложения.



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

Утверждение 2

<Um, · (mod m)> — абелева группа.

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

Докажем, что умножение по модулю m задано на приведенной системе вычетов по модулю m. Действительно, Um покрывает своими вычетами всё Z кроме тех чисел, которые имеют с m общие нетривиальные делители. Результат умножения двух чисел, каждое из которых взаимно просто с m, также будет взаимно просто с m. Согласно свойству сравнений №15, числа одного и того же класса по модулю m имеют с модулем m один и тот же наибольший общий делитель. Это значит, что операция умножения по модулю m не выводит за пределы Um, а значит задана на Um.

Ассоциативность и коммутативность операции · (mod m) следует из ассоциативности и коммутативности умножения, единичным элементом является «1». Каждый элемент множества Um имеет обратный согласно теореме обратимости в силу того, что все элементы Um взаимно просты с m.



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

Кольцом называют непустое множество K вместе с заданными на нем бинарными операциями + и ∙ , если:

а) <K,+> — абелева группа;

б) Операция ∙ ассоциативна;

в) Операция ∙ дистрибутивна относительно + (то есть a∙(b+c)=(a∙b)+(a∙c), (a+b)∙c=(a∙c)+(b∙c));

Кольцо <K,+,∙> называют коммутативным, если операция ∙ коммутативна.

Кольцо <K,+,∙> называют кольцом с единицей, если x∙e=e∙x=x.

Полем называют коммутативное кольцо с единицей <P,+, ∙ >, в котором каждый ненулевой элемент обратим по операции ∙ .

Утверждение

<Zp,+(mod p), ∙ (mod p)> — поле, если p – простое число.

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

Согласно утверждению 1, <Zp,+(mod p)> - абелева группа, причем в качестве нулевого элемента выступает 0Zp. Поскольку Zp покрывает своими вычетами всё множество целых чисел, а операция умножения не выводит целые числа за пределы Z, то и операция умножения по модулю p не выводит за пределы Zp. То есть операция ∙ (mod p) задана на Zp.

Ассоциативность и коммутативность операции ∙ (mod p) следует из аналогичных свойств операции умножения, дистрибутивность умножения по модулю p относительно сложения по модулю p следует из дистрибутивности умножения относительно сложения.

В качестве единицы по операции ∙ (mod p) выступает 1Zp.

Итак, <Zp,+(mod p), ∙ (mod p)> — коммутативное кольцо с единицей. А поскольку в силу простоты p все элементы, кроме нулевого, взаимно просты с модулем p, то, по теореме обратимости, обратим по операции ∙ (mod p).

Следовательно, по определению поля, <Zp,+(mod p),∙(mod p)> — поле.

□

Из курса алгебры мы знаем, что поле, содержащее конечное число элементов, называется конечным полем. Конечные поля называются полями Галуа по имени их первооткрывателя, Эвариста Галуа.

Число элементов в поле называется его мощностью. Все поля одинаковой мощности изоморфны друг другу. Таким образом, любое поле, мощность которого есть простое число, изоморфно <Zp,+(mod p),∙(mod p)> для подходящего p.

Поле <Zp,+(mod p),∙(mod p)> иначе обозначается GF(p), то есть поле Галуа мощности p.

Кроме полей GF(p) существуют поля составной мощности. Различают GF(2α), GF(pα) (где p – простое число, не равное 2 ). В настоящей главе мы будем рассматривать поля GF(p), получим для таких полей некоторые результаты, а затем, во второй главе, обобщим их и на другие конечные поля.