Лекции по алгебре - Фаддеев Д.К.
Скачать (прямая ссылка):
Если модуль есть простое число р, то все классы, кроме нулевого, примитивны, так что ф(р) = р— 1.
Предложение 8. Сравнение ах = Ь (mod т), если а взаимно просто с т, имеет единственный класс решений.
Доказательство. Пусть а' — решение сравнения ах == = l(modm). Ясно, что а'Ь есть решение сравнения ax^b(mod m), ибо a (a'b) = аа'¦b = 1 ¦b (mod m). Если X0— какое-либо решение сравнения ах = Ъ (mod m), т. е. ах0 = b(mod m), то а'ахо = = a'b (mod m), откуда хо = a'b (mod m), ибо а'а == 1 (mod m).
В терминах классов предложение 8 означает, что возможно деление на примитивный класс: уравнение ах = 5 имеет единственное решение X = a~lb.
Если модуль m есть простое число, то все классы, кроме нулевого, примитивны, так что в этом случае возможно деление на любой классу кроме нулевого.
Имеет место следующая теорема, носящая имя Эйлера.
Теорема Эйлера. Если а um взаимно просты, то аФ(«) == і (mod m).
Доказательство. Пусть ах, а2, ак — числа, взятые по одному из каждого примитивного класса, так что k = ф(т). Пусть а взаимно просто с т. Тогда числа ааи аа2, aak тоже взаимно просты с т, т. е. принадлежат примитивным классам. Все они попарно несравнимы между собой. Действительно, если ой,- = г= ааj(mod т), то в силу предложения 5 а,- == а, (mod т), что возможно только если U1 и uj равны. Итак, числа ааи аа2, aak лежат в разных классах и, так как их число равно числу классов, среди них имеется по одному из всех классов («10 человек в 10 комнатах, ни в одной нет двоих, следовательно, все комнаты заняты»). Поэтому числа аа,, аа2, aak сравнимы с а\, а2, ... ..., аи, расположенными, быть может, в другом порядке. Запишем это:
аа, =s aty, аа2 =¦ ah,
(mod пі)
aak = aih.
НЕКОТОРЫЕ ОБЩИЕ ПОНЯТИЯ АЛГЕБРЫ
2t
Здесь і\, І2, ік — те же числа 1, 2, .... k, но в другом порядке. Перемножив эти сравнения, получим
ака\а2 ... Uk=UixU12 ... o/ft,(modm).
Но CLi1CLi2 ... aik — axa2 ... ak, так как сомножители различаются только порядком. Итак,
ака\й2 ... Uk = UxU2 ...a*(modт).
Число aia2 ... uk взаимно просто с т, и на него можно сократить фбе части последнего сравнения. Поэтому ak = l(modm), и остается- вспомнить, что k = ф(т).
В терминах классов теорема Эйлера выглядит так: если а — примитивный класс по модулю т, то а^т) = \.
Важным частным случаем теоремы Эйлера является теорема Ферма: если р — простое число и а не делится на р, то ар~{ = E= l(modp). Она непосредственно следует из теоремы Эйлера, ибо q>{p) = p — 1. Теорему Ферма часто записывают в равносильной ,форме ap = a(modp). В этой записи предположение о том, что а не делится на р, становится излишним.
Теорема Эйлера дает возможность в явном виде записывать ,класс, обратный к данному примитивному классу. Именно, а-1 = '.— й(р(т>_1.
§ 3. Некоторые общие понятия алгебры
1. Группы. В теории сравнений мы встретились с новым явлением, имеющим большую принципиальную важность. Мы обнаружили математические объекты, именно, классы по модулю, не 'являющиеся числами, но над которыми мы имеем возможность совершать алгебраические действия. Свойства этих действий напоминают свойства действий над числами. Подобного рода системы объектов возникают в математике в разнообразных ситуациях, и это делает естественной и необходимой формализацию Возникающих на этом пути более общих понятий.
Полугруппой называется множество, в котором определено действие, сопоставляющее каждой упорядоченной паре злємєеітов третий—результат действия. Действие предполагается ассоциативным. Полугруппами являются: множество целых неотрицательных чисел относительно действия сложения, то же множество относительно действия умножения (это совсем другая полугруппа), множество классов по модулю относительно умножения. Во всех этих примерах действие коммутативно.
Полугруппа называется группой, если в ней существует нейтральный элемент е такой, что при всех а из группы а*е —
е * а — а (через * обозначен знак действия), и для каждого элемента а существует обратный а-1 такой, что a*a~l = а-1 *а = е.
22
ЦЕЛЫЕ ЧИСЛА
(ГЛ. I
Примерами групп могут служить: группа всех целых чисел относительно сложения, группа положительных рациональных чисел относительно умножения, группа классов по модулю относительно сложения, группа примитивных классов по модулю относительно умножения. Все эти группы коммутативны. В качестве примера некоммутативной группы рассмотрим множество непрерывных строго возрастающих функций на [0, 1], со значениями Ф(0) = 0, ф(1)= 1, т. е. функций, осуществляющих взаимно однозначные отображения промежутка [0, 1] на себя, по отношению к действию суперпозиции, т. е. подстановки функции в функцию, так что (ф * f) (х) = ф(ф(х)). Нейтральным элементом здесь является функция ф(х) = х, осуществляющая отображение каждой точки промежутка на себя. Обратным элементом является обратная функция, ассоциативность очевидна. Рассмотрим функции фі = Xi и <р2 = sin-^-'. Обе они принадлежат рассматривае-
мому множеству. Далее, (ф, * ф>) (х) = I sin -— J , а (<р2 * ф,) (х) =
