Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 24
Текст из файла (страница 24)
р.~ ~, где р; — простые числа, которые делят либо а, либо Ь, и некоторые показатели степени могут быть равны О. Пусть т(з) = пйп(а(1),6(1)) и М(з) = пих(а(1),Ь(1)) для 1 < г < Ь. Тогда НОД( 6) ~00 ~Р) ~Р) ™® ) =Рз Рз Рз '''Рь мбц мГз~ м(з> м00 (а, ) =Рг Рз Рз '' Рь Применим теорему 3.49 в случае, когда а = 195000 и Ь = 10435750. Разложения на простые множители чисел а и Ь имеют вид а = 2 3~5~13 и 6 = 2г5 13 19 Таким образом, НОД(195000 10435750) 2т'"гз,цЗ ьы,о)был(4,з>13 ыы,з>19т'що,ц 2~3о5 13г19о 2гбз13~ 3250 НОК(195000, 10435750) = 2 '"~~'ЦЗ~~"ОЮ)5~'"~~'ц13 '"ыс019~'"~о Ц = = 2 3'5413з19г = 626145000. Следующая теорема вытекает из теоремы 3.49.
Доказательство предоставляется читателю. ТЕОРЕМА 3.50. Если а и 6 — положительные целые, то НОД(а, Ь) НОК(а,6) = аЬ. ° УПРАЖНЕНИЯ 1. Разложите каждое из следующих целых чисел на простые множители. а) 728 б) 1599 (используйте равенство 1599 = 1600 — 1) в) 4899 г) 131 д) 523 2. Используйте теоремы данной главы для нахождения НОД и НОК следующих пар чисел: а) 162 и 12 б) 71 и 23 в) 72 и 30 г) и. 'и (и + 2)! д) 75 и 99 3. Два простых числа а и Ь называются числами-близнецами, если разность между ними равна 2, т.е. если а+2 = Ь.
Например, 3 и 5 являются числами- близнецами. Найдите три другие пары чисел-близнецов. 4. Является ли среднее арифметическое двух простых чисел-близнецов простым числом? 5. Если а и Ь вЂ” простые числа, следует ли отсюда, что аз+ба — простое число? 6. Объясните, почему для любого положительного целого числа и все числа и! + 1, и! + 2, и! + 3, и1 + 4, ..., и! + и являются составными. Что данный факт говорит о расстоянии между простыми числами? РАДЕЛ З.б. Сравнения 149 7. Покажите, что числа 479001603 и 479001607 не являются простыми, используя предыдущее упражнение и калькулятор. 8.
Если ры рз, рз, ..., р„— первые и последовательных простых чисел, то слеДУет ли отсюДа, что Рг Р2 Рз ... Р„+1 (пРоизвеДение пеРвых и пРостых чисел плюс единица) есть простое число. Обоснуйте свой ответ. 9. Покажите, что не существует троек последовательных нечетных чисел, каждое из которых является простым, за исключением тройки (3,5,7). 10. Докажите, что если р и д — простые числа, большие или равные 5, то р+ д или р — о делится на 3 и, следовательно, рз — 92 делится на 24. (Указание: р+ 2 или р — 2 делится на 3 и 9 — 2 или ((+ 2 делится на 3.) !1. Докажите, что если а = р',( ) р'( ) и Ь ) а, то Ь = р,(~) р„( ), где 0 < Ь(4) < а(1) для всех г, и обратно.
12. Пусть а = р',(')р'( )р'( )...р,',( ) и Ь = р,(')р ( )р ( ) р„( ), где р, — простые числа, которые делят или а, или Ь, и некоторые показатели степени могут быть равны О. Пусть т(1) = ппп(а(1),6(1)) и М(г) = щвх(а(1),Ь(1)) для 1 < 1 < Ь. Затем докажите, что Н ОД ( о ~ 6 ) р ( 1 ) р ( 2 ) ( 3 ) ™ ( ) м(ц м(2) м(з) м(ь) 3.6. СРАВНЕНИЯ В примере 2.52 изучалось отношение 112 на множестве целых чисел, определенное как 112 = ((а,Ь): а — 6 = 5 Ь). Отношение эквивалентности, порожденное таким разбиением, называется "сравнением по модулю 5".
Фактически такие разбиения можно построить для любого положительного целого числа и, как это было сделано для п = 5. ОПРЕДЕЛЕНИЕ 3.51. Пусть п — положительное целое число. Целое число а сравнимо с целым числом Ь по модулю и, что обозначается а с— а Ь (щод и), если и делит (а — Ь) . Следующая теорема доказывается по аналогии с примером 2.52. ТЕОРЕМА 3.52. Отношение: — для фиксированного и является отношением эквивалентности на множестве целых чисел.
Это означает, что а) а = а (пюд и) для каждого целого числа а; б) если о = Ь (глод п), то Ь = а (гпод и) для целых чисел а и Ь; в) если а ь— а 6 (шод п) и 6 = с (пюд и), то а = с (гпог! п) . ОПРЕДЕЛЕНИЕ 3.53. Пусть и — положительное целое число. Множество всех классов эквивалентности по модулю п обозначается Я„и называется множеством классов вычетов ло модулю л. 150 ГЛДВА 3. Лазике, целые числа ц доказательства Классы вычетов по модулю п представляют собой новые объекты.
Они являются классами эквивалентности. Элементы каждого класса эквивалентности сравнимы между собой по модулю п. Например, пусть и = 3. Имеется три класса эквивалентности по модулю 3, так что множество гз = ([0], [1], [2]) содержит три элемента. Элементы Яз — классы эквивалентности и, следовательно, множества. Эти три множества содержат О, 1 и 2, соответственно, как свои имена. В каждом из этих классов эквивалентности все элементы сравнимы между собой по модулю 3, так что а = Ь (шос1 3) тогда и только тогда, когда а и Ь принадлежат одному и тому же классу эквивалентности — классу вычетов. Таким образом, [0] = (... — 0,-3,0,3,0,0...); [1] = (...
— 8, — 5, — 2, 1, 4, 7...); [2] = (... — 7, — 4, — 1,2,5,8...). Теперь нам нужно определить операции между классами вычетов по модулю п. Отношение сравнимости =, как подсказывает само обозначение, имеет много общего с отношением равенства. Но с отношением сравнимости по модулю и связано больше ограничений, чем с аналогичным ему отношением равенства.
ТЕОРЕМА 3.54. Отношение сравнимости обладает следующими свойствами: а) если а = Ь (гаос1 и) и с = с( (шос1 п), то а+ с = 6+ с1 (шос( п) и ас = Ы (гпос( и); б) если а = 6 (шос1 псп), то а = Ь (шос1 гп) и а = Ь (шос1 п). ДОКАЗАТЕЛЬСТВО. Мы докажем пункт (а); часть (б) предлагаем доказать читателю. По определению, если а = 6 (гпос1 и) и с = с1 (гпос1 п), то а — 6 = ип и с — с1 = ип для некоторых целых чисел и и и.
Таким образом, (а+с) — (Ь+с() =(а — 6)+(с — с() =и и+и п=(ич и) п для некоторых целых чисел и и и, и а+ с = 6+ с1 (шос1 и). Кроме того, а = Ь+ ип и с = с1+ ип, так что ас = (Ь+ (ип))(с1+ (ип)) = Ьс1 + 6(ип) + с1(ип) + иипз = Ы+ (Ьи + исс+ иип) и. Таким образом, ас — Ы = (Ьи + ис1+ иип)п и ас = Ьс1 (гаос( и). ПРИМЕР 3.55.
Пусть п = 3. 1 э— э 7 (шос1 3), 2 = — 4 (шос1 3). Из теоремы 3.54 (а) следует, что 1+ 2 = 7+ (-4) (гпос1 3), а также, что (1)(2) = (7)( — 4) (шос1 3), что верно, поскольку 2 — ( — 28) = 30 = 3 10 = 3 /с. РАЗДЕЛ З.б. Сравнения 151 ТЕОРЕМА 3.56. Для произвольного положительного целого числа и, а) если т = т' (пюа' и), 0 < т < и и 0 < т' < п, то т = т'; б) если а — любое целое число и и — положительное целое число, то имеется целое число т, где 0 < т < п такое, что а = т (гаоа п).
Целое число т— остаток от деления а на п, поэтому а = пд+ т. ДОКАЗАТЕЛЬСТВО. Утверждения теоремы следуют непосредственно из алгорит- ма деления. Часть (а) утверждения теоремы гарантирует, что классы вычетов по модулю и обладают тем свойством, что классы вычетов, порожденные неотрицательными целыми числами, меньшими, чем и, различны. Таким образом, [0), [Ц, [2],..., [и — 2], [п — Ц вЂ” различные множества относительно сравнимости по модулю п. Часть (б) показывает, что каждое целое число а сравнимо по модулю п с одним из целых чисел 0,1,2,...,и — 1. Итак, любое целое число а принадлежит одному из п различных классов эквивалентности [0),[Ц,...,[и — Ц. Проведенное рассмотрение служит объяснением к следующей теореме. ТЕОРЕМА 3.57. Пусть п — произвольное положительное целое число.
Тогда Я„, множество классов вычетов по модулю п, состоит точно из п различных классов вычетов [0), ) Ц, [2],..., [п — Ц, представленных различными остатками, которые могут быть получены при делении на п. Кроме того, для 0 < т < и, класс вычетов [т] состоит точно из тех целых чисел а, для которых а = т (пюб п). Следующая теорема является простым следствием предыдуших теорем, которое, тем не менее, часто оказывается полезным. ТЕОРЕМА 3.58. Если а = пд+ т и 6 = ид' + т' для 0 < т < п и 0 < т' < п, то т = т' тогда и только тогда, когда а = 6 (пюс1 и). В целом, при работе с классами вычетов по модулю и желательно для его представления выбрать в классе наименьшее неотрицательное целое число.
Это особенно важно для сложения и умножения классов вычетов в Я„, поскольку необходимо, чтобы сумма и произведение все еще представлялись целыми числами, которые находятся между 0 и п — 1. Это приводит к следующему определению. ОПРЕДЕЛЕНИЕ 3.59. Пусть х,„— множество классов вычетов по модулю п. Для любого заданного целого числа т существует целое число т такое, что 0 < т < п — 1 и [т] = [т) или ти = т (щи и). При этом говорят, что [[ти])„ = т. ПРИМЕР 3.60.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
