Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 25
Текст из файла (страница 25)
Для п = 5 получаем Яз = ([0], [Ц, [2], [3], [4]) = = ([т]: О < т < 5) . 152 ГЛЯВА 3. Лоаика, целые числа и доказательства На множестве Я„можно определить операции сложения и умножения. Если [а] — класс вычетов по модулю и, содержащий а, и (6) — класс вычетов по модулю и, содержащий Ь, то сложение и умножение определим соотношениями [а] йз [6] = [а + Ь) = [[а + Ь]]„, [а] О [Ь] = [а Ь) = [[а 6]]„, где сложение и умножение в центре и справа осуществляется между целыми числами, а сложение и умножение по левую сторону выполняется между классами эквивалентности. Использование предыдущей теоремы показывает, что операции сложения и умножения таких классов эквивалентности — классов вычетов — определены правильно; т.е.
определение не зависит от представителей классов вычетов. Например, если [а] = [с], то результат сложения не должен зависеть от того, используем мы [а) или [с). Иначе говоря, если [а] = [с] и (Ь) = [4], то [а] Ю [6) = (с] Ю [г1] и [л]О(6) =(с) ОИ ПРИМЕР 3.61. Для и = 5 и Ез = [[0],(Ц, [2), [3], [4)) находим, что [2] В [4] = [2+4) = [6! = [Ц, поскольку 6 = 1 [гпог1 5); [2] О [4] = [2 4] = (8] = (3], поскольку 8 = 3 [гпог1 5). Вычисляя все возможные суммы и произведения, можно создать таблицы "сло- жения" и "умножения" для классов вычетов по модулю 5.
[а] Щ [Ь] [о] [1] (2] [з] [4] [а] О [Ь] [о] [1] [2] [з] [4] Теорема 3.57 показывает, что для произвольного положительного целого числа и множество целых чисел может быть разбито на и непересекающихся множеств, или классов эквивалентности. В дальнейшем мы часто будем возвращаться к этим множествам, интересуясь их представителями. [0] [Ц [2] [з] [4) [0] (Ц [2) (3] (4) [0] [Ц [2] [3] [4] [Ц [2] [з] [4] [о] [2] [3] [4) [О) [Ц [з) [4) (о) [Ц [2) [4] [0) [Ц (2) [3) [0] [О) [О) [0) (О) [0] [Ц [2! [3) [4] [о) [2] [4) [Ц [з] [0] (3! [Ц [4) [2] [о] (4! [з] [2! [1! РАздел 3.в. сравнения 153 ОПРЕДЕЛЕНИЕ 3.62.
Если Ь э— а т (тоо и) для положительного целого числа и, то говорят, что г есть вычет числа Ь по модулю и. Полная система вычетов по модулю и есть множество Я = (ты тз,..., т„), где пересечение множества Я с каждым классом вычетов по модулю и содержит точно одно целое число, т.е. о содержит одного и только одного представителя из каждого такого класса вычетов. Полная система вычетов (0,1,2,...,(и — 1)) называется первичной системой вычетов. Если Ь вЂ” целое число, Ь = т (атос( и) и 0 < г < и — 1, то этот единственный первичный вычет по модулю и обозначается через г = [[Ь]]„. Приведенная система вычетов по модулю и есть подмножество полной системы вычетов, состоящее только из тех целых чисел, которые являются взаимно простыми с и, т.е.
(т: т Е Я и ИОД(т, и) = 1). Полная система вычетов получается путем выбора одного целого числа из каждого класса вычетов [0], [Ц,..., [и — Ц множества Я„. Итак, для и = 6, (24,7, — 58,40,113) — полная система вычетов по модулю 6, так как Очевидно, что (0,1,2,3,4,5) является полной (и притом первичной) системой вычетов по модулю 6. По определению, [[24]]е = 0 и [[ — 58]]е = 2.
Поскольку все элементы любого класса вычетов по модулю и сравнимы один с другим, но не являются таковыми по отношению к элементам другого класса вычетов, каждое целое число сравнимо ровно с одним элементом полной системы вычетов. Проведенные рассуждения приводят к следующей теореме. ТЕОРЕМА 3.63. Если и — положительное целое число, (тг,тз,...,т„) — полная система вычетов по модулю и и а — некоторое целое число, то а ь— э ть (щоо и) для одного и только одного Ь, 1 < и < и.
Элементы полной системы вычетов (24,7, -58,15,40,113) и первичной (полной) системы вычетов (0,1,2,3,4,5) по модулю 6, которые являются взаимно простыми с и = 6, содержат в себе, соответственно, множества (7,113) и (1,5). Поэтому оба последних множества являются приведенными системами вычетов по модулю 6. При этом говорят, что (1,5) является первичной приведенной системой вычетов по модулю 6.
Следующая теорема показывает, что приведенная система вычетов содержит больше существенной информации о целых числах из Я, чем система чисел, взаимно простых с и. Доказательство теоремы предоставляется читателю. ТЕОРЕМА 3.64. Пусть и — положительное целое число и (тг,тз,...,ть) — приведенная система вычетов по модулю и. Если а — целое число, взаимно простое с и, то а = г (щоо и) для одного и только одного з, 1 < з < Й. 24 = 0 7=1 — 58 = 2 15 = 3 40 = 4 113 = 5 (гпос1 6), (гной 6), (пюс1 6), (гпог1 6), (пюа 6), (гной 6), поэтому поэтому поэтому поэтому поэтому поэтому 24 6 [0]; 7е[Ц; — 58 е [2]; 15 6 [3]; 40 6 [4]; 113 е [5].
164 ГЛАВА 3. Лазике, целые чосле и оокезетельстее Если дана одна система вычетов, имеется несколько способов воспроизвести другие системы вычетов. Один из способов состоит в прибавлении одного и того же целого числа к каждому вычету в полной системе вычетов. Иной способ демонстрирует следующая теорема. Доказательство предоставляется читателю. Поскольку НОД(6,35) = 1, имея полную систему вычетов (0,1,2,3,4,5) и приведенную систему вычетов (1, 5) по модулю 6, получаем, что (35 О, 35 1,35 2, 35 3,35 4, 35 5) и (35 1, 35 5) являются, соответственно, полной и приведенной системами вычетов. Но [[ОЦб Ц1Це [[2Це [[ЗЦе [[4Це Ц5Ц. [[о]] = о ([35Ц, = 5 [[70Це = 4 [[107Це = 3 [[140Ц, = 2 [[175Це = 1 0 и [[35. ОЦе 1 [[35 1Ц, 2 [[35 2Це 3 [[35 ЗЦе 4 [[35 4Це 5 [[35 5Це Таким образом, в результате умножения каждого элемента г, полной или приве- денной системы вычетов по модулю и на целое число а, взаимно простое с и, получаем представителей тех же классов вычетов, возможно, в другом порядке.
° УПРАЖНЕНИЯ 1. Вычислите а) [[37Ц4', 6) [[93Цз, г) [[149Цгт', 2. Вычислите а) )[ЗЗЦ; б) [[47Цсл 3. Вычислите а) [[8!Це, 6) [[1+ 2+ 3+ 4+ 5+ 6+ 7+ 8+ 9+ 10Цз,' в) [[1г + 2г + 3' + .. 25г Ц . г) [[(146)гЦгг 4. Покажите, что аг = Ьг (шод и) не имеет следствием а = Ь (щи и). 6. Покажите, что если а — нечетное целое число, то аг = 1 (шод 8). 6. Постройте таблицу сложения для классов вычетов по модулю 4. 7. Постройте таблицу умножения для классов вычетов по модулю 4. 8. Постройте таблицу сложения для классов вычетов по модулю 7. 9. Постройте таблицу умножения для классов вычетов по модулю 7. 10. Используя таблицы сложения и умножения для классов вычетов по модулю 5, приведенные ранее, найдите в лз решения следующих уравнений: а) х + [3] = [5); 6) [3].х = [2); в) [4) х = [3); г) [2] х = [1]. в) [[48Цгз в) [[49Ц гт г) )[146Цгг ТЕОРЕМА 3.66.
Пусть и — положительное целое число и (гы гг,..., гь) — полная [приведенная) система вычетов по модулю и. Если а — целое число, взаимно простое с и, то (агы агг,..., ага) — также полная [приведенная) система вычетов. РлздеЛ з.в. сравнения 155 11. Используя таблицы сложения и умножения для классов вычетов по модулю 4 из приведенных выше упражнений, найдите в Яв решения следующих уравнений; а) х + (3] = [2]; б) [3! х = [2]; в) [2] х = [2]; г) (2] х = [0].
12. Используя таблицы сложения и умножения для классов вычетов по модулю 7 из приведенных выше упражнений, найдите в Ят решения следующих уравнений; а) х + [5] = [2]; б) (3] х = [4]; в) [2]. х = [5]; г) [4] х = [6]. 13. Докажите, что если а ив з Ь [пюб тп), то а = Ь [шоб т) и а з— а Ь [пюб и). 14. Докажите, что если ас = Ьс (пюб и) и целые числа с и и — взаимно простые, то а = Ь [шоб и). 15. Докажите теорему 3.64. Пусть и — положительное целое число, и (ты ге, ..., гь) — приведенная система вычетов по модулю п.
Если а — целое число, взаимно простое с п, то а ге г (гной и) для одного и только одного у, 1< у </с. 16. Докажите теорему 3.65. Пусть п — положительное целое число, и ггытз, ...,гь) — полная [приведенная] система вычетов по модулю и. Если а— целое число, взаимно простое с п, то (агы ага,..., ать) — тоже полная [приведенная] система вычетов. РАЗДЕЛ 4.7.
Функции 157 ПРИМЕР 4.3. Пусть А = ( — 2, — 1, О, 1, 2) и В = (0,1,2,3,4,5). Функция Г" А- В определена соотношением )'(з) = Фа+ 1. Если Е = (1,2), то 1(Е) = (Ь: (а, 6) Е 7' для некоторого а из Е) = = (6: Ь = 1(а) для некоторого а из Е) = = (2,5) является образом Е при отображении 7". Если Г = (0,2, 3, 4, 5) С В, то '(Р) = (Ь: существует а е А такое, что 1(а) = Ь) = = ( — 1,1, — 2,2) является прообразом Л, где — 1 Е 1 '(Л), т.к. 1( — 1) = 2, 1 Е г' '(Л), т.к. )'(1) = 2, — 2 Е,Г" '(Г), т.к. Д вЂ” 2) = 5 и 2 Е,Г" '(Л), т.к. 1(2) = 5.
Заметим, что элементы О, 3 и 4 не вносят никаких элементов в 1 '(Л), поскольку они не принадлежат области значений функции 1. Прообраз может быть пустым. Так, например, в случае И' = (0,3) прообраз г" '(И') пуст, поскольку не существует такого а е А, для которого г'(а) = 0 или 7"(а) = 3. Область значений функции Г" имеет вид Д(А) = (Ь: )'(а) = Ь для некоторого а Е А) = = (1,2,5). Элементами г'(А) являются те и только те элементы области потенциальных значений В, которые "используются" функцией г'.
П Мы уже отмечали, что если Л вЂ” отношение на А х В, а  — отношение на В х С, то можно определить отношение ЯоЛ на А х С, называемое композицией Я и Л. Если Л и Я вЂ” функции, то Яо Л вЂ” тоже функция, называемая композицией Я и Л. Следующая теорема описывает некоторые полезные свойства композиций. ТЕОРЕМА 4.4. Пусть д: А — В и г:  — С.
Тогда а) композиция 7' о д есть функция из А в С, что может быть записано как 1од:А — ~С; б) если а Е А, то (Г о д)(а) = Г(д(а)). ДОКАЗАТЕЛЬСТВО. а)Еслид:А- Ви1:В- С,тодСАхВи1СВхС. По определению композиции отношений 7" о д с А х С. Пусть (а,с) Е 1 о д и (а,с') е 1 од. Требуется показать, что с = с'. Поскольку (а, с) е 1 од, существует такой элемент Ь Е В, что (а, 6) Е д и (6, с) Е 7". Точно так же, поскольку (а,с') Е Г" од, то существует такой элемент 6' Е В, что (а,Ь') Е д и (Ь',с') Е Г'. Но д является функцией, так что (а, Ь) е д и (а, Ь') е д, откуда следует равенство 6 = 6'. Следовательно, (Ь', с') = (Ь, с') Е 1 и (Ь, с) Е г'.
Поскольку 7" также является функцией, то с = с'. Поэтому г" о д — функция из А в С. б) Если д: А — В и а Е А, тогда существует такое Ь из В, что Ь = д(а). Поскольку Ь Е В 1:  — С, имеется некоторое с Е С, для которого (Ь, с) Е,г", т.е. с = 1(6). Но Ь = д(а), так что 1(д(а)) = 1(6) = с = (Г" о д)(а), поэтому (а, Ь) Е д и (Ь, с) Е Х, откуда следует, что (а, с) Е,( о д. 188 ГЛЯ84 4.
Функции и матрицы Поскольку композиция отношений обладает свойством ассоциативности (см. теорему 2.31), то, в частности, имеет место следующая теорема. ТЕОРЕМА 4.8. Пусть 1: А - В, д; В - С и Ь: С - Р. Тогда Ьо (д о 1) = (йод) о 1, т.е, композиция функций ассоциативна. ПРИМЕР 4.8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
