Глухов М. М. Алгебра том 1 (1016678), страница 17
Текст из файла (страница 17)
П С л е д с т в и е 1. Для любых целых чисел а, Ь, с и натурального й справедлива импликация: а = 0(нюсе т) =» а * с = Ь * с(пюс1 т), а" = 0~(нюсе т), а = Ь(пюс1т) ~ а/й = Ь/й(пюс1т), где * — любая из операций+, —, Приведенными свойствами сравнений можно воспользоваться для нахождения остатков от деления чисел на заданное число т. С л е д с т в и е 2. Для любых целых чисел а, Ь и любой операции * Е 1+, —, ) верно равенство: т (а*Ь) = т (т (а) *т (Ь)). П Так как а = т (а)(пюс1 т), Ь = т„,(0)(нюсе т), то по теореме 2 6) а*Ь = т~(а) *т~(0)(пюйт). Отсюда по определению 1 имеем (1).
П П р и м е р 1. Найти остаток от деления числа а = 12814в — 1481гэ на число 13. По следствию 2 т1з(а) = т1з(г1з(128'4з) — т1з(148'гэ)). Поэтому найдем сначала остатки т1з(12814з), т1з(148~~э). Заметим, что 128 = — 2(тосе 13). Отсюда последовательно находим: Так как 148 = 12. 12+ 4, то 12814з = (1281г)1г 1284: — 3(пюс113), и потому т1з(12814з) = 3. Аналогично найдем, что т1з(1481гэ) = 5. В итоге имеем искомый остаток: т1з(а) = т1з(3 — 5) = т1з( — 2) = 11. т ~ а — Ь (=» т ~ (а1 — 01)И. 90 91 где * — любая из операций +,—, (т.
е. сравнения можно почлеиио складывать, вычитать и перемножать). в) Если й — общий делитель чисел а, Ь, т из Ж, то а = Ь(пюс1 т) ~ а(с1 = 0(сЦгпо6 т(6), (т. е. обе части сравнения и модуль можно делить и умножать иа одно и то же число). г) Если й — общий делитель чисел а, Ь и (И, т) = 1, то (т. е. обе части сравнения можно умножать и делить иа число, взаимно простое с модулем). П а) Непосредственно из определения 1 видно, что отношение сравнимости по модулю т рефлексивно, симметрично и транзитивно, т. е. является отношением эквивалентности. 6) Из условия, согласно критерию сравнимости чисел, имеем: а — Ь = = тд1, с — Й = тдг, т. е.
а = Ь+ тв1, с = И+ туг, где в1,дг е У. Складывая, вычитая и перемножая последние равенства, получим: а + с = Ь+ с~ + т(в1 + яг), а — с = Ь вЂ” с~+ т(ч1 — а) ас = Ы+ т(д1с~+ Ь1г + тИг). Отсюда видно, что разность (а * с) — (Ь * й) делится на т при любой операции е Е (+, —, ). Следовательно, а е с = Ь * й(пюс1 т).
в) Так как й — общий делитель чисел а, Ь, т то существуют целые числа а1,01,т1, такие, что: а = а1И, Ь = 016, т = т1И. Отсюда и из определения делимости чисел, учитывая отсутствие делителей нуля в Ж, получим: т ~ а — Ь ~ т1й ~ (а1 — 01)с~ ~ т1 ~ а1 — Ь1. Теперь свойство в) следует непосредственно из теоремы 1. г) Как и в случае в), имеем: 128г ( 2) г (пюс1 13), 1284 = 4г(шос1 13), 128е = 4 ° 3(тосе 13), 1281г = ( — 1)~(тосе 13), т. е. 128 = 4(пюс113), т. е.
1284 3(пюс113) т. е. 128е = — 1(тосе 13), т. е. 1281г = 1(тосе 13). ~ 2. Классы вычетов и операции над ними По теореме 2 а) отношение сравнимости по модулю т является отношением эквивалентности на Ж, и потому множество У разбивается на непересекающиеся классы чисел, сравнимых по модулю т, т. е. дающих одинаковые остатки при делении на т (см. теорему 1.П). О п р ед ел е н и е 2.
Класс всех целых чисел, сравнимых с числом а по модулю т, называют классом вычетов по модулю т и обозначают через [а] . Множество всех классов вычетов по модулю т обозначим через Ж/т. Из определения 2 имеем: [а] =(хай:т (х) =г (а)), [а] = [Ь] ~ а: — Ь(тосе т). (2) Так как различные остатки от деления целых чисел на т исчерпываются числами О, 1,..., т — 1, то число классов вычетов по модулю т равно т, и У/т = ([0]тэ [1]пь~ . 1[т — 1]пъ). Определим на множестве Ж/т операции сложения (+) и умножения О п р е д е л е н и е 3. Для любых [а]~, [Ь],„Е У/т положим: [а]т + [Ь]т = [а + Ь], [а],„[Ь],„= [аЬ]т.
Таким образом, чтобы сложить (перемножить) классы [а], [Ь]~, нужно выбрать из них по одному представителю, сложить(перемножить) их как числа и взять класс, содержащий полученное число. В определении 3 в качестве таких представителей выбраны числа а и Ь. Однако в классах [а]~, [Ь],„содержится много других чисел, и мы заранее не уверены в том, что результат сложения (умножения) классов не зависит от выбора представителей.
Если бы результат зависел от выбора представителей, то, складывая одни и те же классы, мы могли бы получать разные результаты. Это бы означало,что операции определены не корректно. Докажем, что определение 3 корректно. Действительно, пусть, а1 Е [а],Ь1 е [Ь] . Тогда а1 = а(пюс1т), Ь1 = Ь(той) т и по теореме 2 имеем: а1+ Ь1 = — а+ Ь(шос1т),а|Ь1 = — аЬ(шос1т), т. е. [а1+ Ь1]~ = [а+ Ь]~,[а1Ь1]~ = [аЬ] . Следовательно, результаты операций над классами не зависят от выбора представителей, т.
е. операции определены корректно. Т е о р е м а 3. Множестпво Ж/т всех классов вычетов по модулю т с определенными выше операциями сложения и умножения является коммутативным кольцом с единицей. (Оно называетпся кольцом вычетов по модулю т.) П Так как операции сложения и умножения над классами сводятся к соответствующим операциям над целыми числами, то обе они ассоциативны и коммутативны, кроме того, операция умножения дистрибутивна относительно сложения. Очевидно, что классы [0],„и [1],„являются в Ж/т нейтральными элементами относительно операций соответственно +,, и для любого [а],„класс [ — а],„является противоположным элементом, т. е. -[а] = [-а] .
П Следующее утверждение описывает в кольце Ж/т обратимые элементы и делители нуля. Т е о р е м а 4. В кольце Ж/т каждый элементп [а] ф [0]~ или обратпим, или делитель нуля, причем: а) [а],„— обратим ~ (а,т) = 1, б) [а] — делитпель нуля ~ (а, т) ~ 1. П а) Пусть (а, т) = 1. Тогда по следствию из теоремы 4.1Ч существуют такие У, ~ Е Ж, что а0+т7 = 1.
Следовательно, [аУ+тУ]~ = [1]~, и согласно определению 3: [а]пъ [Р]пъ + [т]ш [~]т = [1]пъ. Отсюда и из равенства [т],„= [0],„имеем: [а]„, [У],„= [1] . Следовательно, элемент а,„обратим, и [а],„1 = [У]~. б) Пусть (а, т) = й > 1. Тогда а = йа1, где а1 Е Ж, и (а) [ — ] = [ — т] = (а~т] = (О) Я Гт1 Так как [а],„~ [0],„по условию, ~-~-~~ ~ [0],„в силу неравенства 1\ т с~ > 1, то [а]~ — делитель нуля. П 92 93 Из теорем 3 — 4 получаем С л е д с т в и е 1. Порядок мультипликативной группы (Ж/т)* кольца Ж/т равен числу натуральных чисел, не превосходящих т и взаимно простых с т. С л е д с т в и е 2. Кольцо Ж/т является полем тогда и только тогда, когда т — простое число.
(В последнем случае оно называется полем вычетов по модулю т.) Рассмотрим вопрос о вычислении порядка группы (Ж/т)*. О п р е д е л е н и е 4. Отображение ~р: Я вЂ” Я, сопоставляющее каждому числу т Е Я число ~р(т), равное количеству натуральных чисел а < т и взаимно простых с т, называется функцией Эйлера. П р и м е р 2. ~р(1) = 1, ~р(2) = 1, ~р(10) = 4, ~р(р) = р — 1 для любого простого р. Из определения 4 и следствия 1 теоремы 4 имеем: ~(Ж/т)*~ = ~р(т). Приведем формулу для вычисления ~р(т). Т е о р е м а 5. Если натуральное число т имеет каноническое разложение т = р~'р~'...
р~', то 1 1 1 ~р(т) = т(1 — — )(1 — — )... (1 — — ). р1 рг рз П Найдем сначала ~р(р~'). Так как р, — простое число, то (а, р,"*) ~ 1 в том и только том случае, когда р, ~ а. Следовательно, написав ряд чисел от 1 до р,' и удалив из него все числа, кратные р,, получим: й, 'Р рь = рг рг' = рч' Теперь для доказательства теоремы достаточно воспользоваться свойством мультипликативности функции Эйлера: Чт~, тг Е Я: Цт~, тг) = 1 =~ ~р(т~, тг) = ~р(т~)~р(тг)) которое мы пока примем без доказательства (оно будет получено попутно при изучении групп в ~ 4.Х1). П Докажем одно из замечательных свойств функции Эйлера.
Т е о р е м а 6. Если натуральные числа а, т взаимно просты, то а"'~ ~ = Цшос1т). (3) П Выпишем по одному представителю из всех классов группы (Ж/т)*: а~, аг,, а„,~,„~. Умножив все эти числа на а, получим ряд чисел: а~а, ага,..., а~~ ~а. (4) По теореме 5 а) 1Ч все числа из (4) взаимно просты с т. Кроме того все они попарно несравнимы по модулю т поскольку в силу теоремы 2 г) а,а = а а(пюс1 т) =~ а; = а (пюс1 т). Отсюда, учитывая, что ~(Ж/т)*~ = ~р(т), получаем: (4) есть систе- ма представителей, взятых по одному из каждого класса множества (Ж/т)*. Следовательно, имеет место система сравнений: а~а: — а,, (пюс1 т), ага = а,,(пюс1т), а„,~„,~а = а,,~,„~(пюс1 т), где г~, гг,..., г„,~ ~ — некоторая перестановка чисел 1,2,..., ~р(т). Перемножив почленно эти сравнения и разделив обе части полученного сравнения на число а~ аг ...
а„~„,~, которое взаимно просто с т, получим (3). П С л е д с т в и е . Если р — простое число и а е Ж, то а) а" ~ = Цшос1р) при (а, р) = 1, 6) а" = а(шос1 р) при любом а. П Для доказательства утверждения а) достаточно заметить, что ~р(р) = р — 1. Утверждение 6) при (а,р) = 1 следует из а) и следствия 1 теоремы 2, а при (а, р) ~ 1 очевидно, поскольку в этом случае а = 0(пюс1р). П Заметим, что утверждение а) следствия впервые доказал Ферма, оно называется малой теоремой Ферма. Теорема 6 была позднее доказана Эйлером и носит название теоремы, Эйлера — Ферма. Она находит широкое применение в математике и ее приложениях и, в частности, может оказаться полезной при нахождении остатков от деления степеней числа на заданное число, при решении сравнений с неизвестными и т.
д. 94 95 Так, в примере 1 для нахождения остатка от деления 12814в на 13 мы нашли предварительно сравнение 12812 = Цшой 13). С учетом теоремы Эйлера — Ферма для его нахождения достаточно заметить, что ~р(13) = = 12. Подчеркнем еще, что при любом простом р поле Ж/р — не числовое, поскольку оно не является подполем поля комплексных чисел. Больше того, оно обладает рядом специфических свойств, не имеющих места в числовых полях. Приведем примеры таких свойств.
У т в е р ж д е н и е 1. Для любого элементпа а 7золя Цр выполняютпся равенства: и) ра = а +... + а = р, где р — арль поля Е7р; р 6) сР=а. П Равенство а) очевидно, равенство 6) следует из утверждения 6) предыдущего следствия. П 3 а м е ч а н и е 1. На практике в целях упрощения записей часто вместо кольца (поля) вычетов Ж/т используют изоморфное ему кольцо (поле) Я„„элементами которого являются наименьшие неотрицательные представители 0,1,..., т — 1 классов. При этом под операциями сложения и умножения понимают обычные арифметические операции над числами с последующей заменой результата остатком от его деления на т. Кольцо Я,„также называют кольцом вычетов по модулю т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
