Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 78
Текст из файла (страница 78)
В частном случае Ь = О можно находить решения уравнения ах = с. Теперь будем искать решения сравнений ах = с (шос(п) в том смысле, что требуется найти такое целое число х, при котором целое число ах сравнимо с с по модулю и. Или, на языке классов эквивалентности, для классов эквивалентности [а) и [с] по модулю п, найти класс эквивалентности [х] такой, что [а] О [х! = [с), где равенство означает равенство множеств. Используя таблицу умножения для Яз (см, раздел 3.6), РЯЗДЕП 70.2. Решеноя сраененоо 425 Зх = 1 (шос1 5). В теореме, приведенной ниже, сформулированы важные свойства сравнимости. Части (а) и (г) доказаны в теореме 3.54. Доказательство остальных пунктов предоставляется читателю.
ТЕОРЕМА 10.5. а) Если а = Ь (пюс1 и) и с = с1 (шос) и), то а + с з— в Ь + с1 (пюс1 и) и ас = Ы (шос1 и). б) Если ас эв Ьс (шос) и) и НОД(с, и) = 1, то а = 6 (пюс) и). в) Если а = Ь (шос) и), то а™ = Ь (шос( и) для всех целых положительных чисел т. г) Если а = Ь (шос) ти), то а = Ь (гпос1 т) и а = 6 (шос) и). д) Для с ф 0 соотношение ас = Ьс (пюс) и) имеет место тогда и только тогда, и когда а = Ь шос( НОД(с, и) у ' е) Если а = Ь (тос) т), а:— 6 (шос) и) и НОД(т, и) = 1, то а = Ь (пюс) ти). В следующих двух теоремах формулируются условия, при которых решение ах = с (пюс) и) существует, и указывается явный вид решения.
ТЕОРЕМА 10.6. Сравнение ах = с (шос1 ти) имеет решением целое число х тогда и только тогда, когда НОД(а,т) [ с. Все целочисленные решения имеют вид с т НОД(а, ги) где с — любое целое число, и для хо существует такое уо, что (хо,уо) является решением уравнения ах + ту = с. ДОКАЗАТЕЛЬСТВО. По определению, ах = с (пюс) т) тогда и только тогда, когда ах — с делится на т, т.е. существует целое число Г' такое, что ах — с = Зт. Это справедливо тогда и только тогда, когда ах+ту = с имеет решение. Целые числа а, т и с фиксированы, и требуется найти целые числа х и у такие, что ах + ту = с.
По теореме 10.1 ах + тиу = с имеет целочис- ленное решение тогда и только тогда, когда НОД(а,т) [ с. Также согласно этой теореме, решение имеет вид и с НОД(а, т) и с НОД(а, т) Анализ таблицы умножения показывает, что [х] = [2] будет решением, т.к. [3] О [2] = [1]. Поэтому можно положить х = 2. Поскольку [2] = (..., — 8, — 3,2,7,12, ...), отмечаем, что каждое число из совокупности х = — 3, х = 7 и х = — 8 является тем значением х, которое удовлетворяет 426 ГЛЯВЯ 10.
Некоторыв специальные вопросы теории чисел где и и и выбраны таким образом, что аи+ гпи = НОД(а, т). По теореме 10.4 все решения имеют вид с т с т НОД(а, тп) НОД(а, т) где с — произвольное целое число. В данном случае необходимо решение только для х. Таким образом, все целочисленные решения ах = с (шос1 т) имеют вид с т НОД(а, т) имеет в точности 7 различных решений по модулю 84, которые имеют вид 84. с хо+ — = хо+12 Ф, 7 где с = 1,2,3,...,7 и (хо, уо) является решением 35х+ 84у = 14, которое равносильно 5х + 12у = 2.
Проверка дает в качестве решения хс = — 2 и уо = 1. Семь различных решений по модулю 84 имеют следующий вид. хо+ 12à — 2+12.1=10 — 2+12 2=22 — 2 + 12 3 = 34 — 2+12 4 = 46 -2 ц- 12 5 = 58 — 2+12 6=70 — 2+ 12. 7 = 82 1 2 3 4 5 6 7 где с — любое целое число. Следующая теорема предоставляет различные решения сравнений ах ив з с (гпог1 т). Поскольку существует конечное число классов эквивалентности по модулю т, может существовать только конечное число различных решений по модулю т. Все они даны в приведенной ниже теореме. Доказательство теоремы предоставляется читателю.
ТЕОРЕМА 10.7. Если НОД(а,т) ~ с, то ах а— з с (шод т) имеет конечное число различных решений по модулю т. Эти решения имеют вид для с = 1, 2, 3,..., НОД(а, т), где для хо существует такое уо, что (хо, уо) является решением уравнения ах+ ту = с. ПРИМЕР 10.6. В силу того, что НОД(35,84) = 7 и 7 ( 14, сравнение 35 х ив з 14 (шой 84) РАЗДЕЛ 10.2. Решения сравнений 427 Когда НОД(а,т) = 1, существует единственное решение сравнения ах = с (пюй т).
Например, рассмотрим сравнение 6х = 7 (шой 55), НОД(6, 55) = 1, и, очевидно, 1 делит 7. Поэтому существует только одно решение по модулю 55, которое имеет вид 1 т 1 55 хо+ = хо+ = хо+55 = хо (пюй 55), НОД(6, 55) 1 где (хв, уо) — решение уравнения ах + ту = с или бх + 55у = 7. Для нахождения хо и уо начнем перебор с возвратом по алгоритму Евклида, как показано в примерах, следующих за теоремой 7.2, получая при этом 6( — 9) + 55(1) = 1 = НОД(6,55). Умножая каждое слагаемое на 7, получаем 6( — 63) + 55(7) = 7, так что хо = — 63 и х = — 63+ 55 = — 8.
П ПРИМЕР 10.9. Решить сравнение 623х = -406 (пюй 84). Число 623 больше, чем модуль сравнения 84, а — 406 является отрицательным. Поскольку разыскиваются решения по модулю 84, выбираем целые числа в диапазоне 0,1,2,...,83, т.к. они являются возможными остатками при делении на 84 и простейшими представителями классов эквивалентности, порожденных сравнимостью по модулю 84. Используя алгоритм деления, получаем 623 = 84 7 + 35, так что 623 = 35 (пюй 84); †4 = 84( — 5) + 14, так что — 406 = 14 (пюй 84). Таким образом, 35х = 14 (пюй 84) равносильно исходному 623х = -406 (пюй 84).
Решение сравнения 35х : — 14 (пюй 84) было найдено в предыдущем примере. П Доказательство следующей теоремы предоставляется читателю. ТЕОРЕМА 10.10. Если а = Ь (пюй иг), а = Ь (шой из), ..., а = Ь (пюй иь) и = НОК(иы из,..., иь), то а = Ь (шой и), и обратно. ° УПРАЖНЕНИЯ 1. Для каких значений и справедливо 75 = 35 (шой и)? 2. Найдите решения следующих сравнений: а) 4х = 3 (пюй 7); б) 27х = 12 (пюй 15); в) 28х = 56 (пюй 49); г) 24х = 6 (пюй 81); д) 91х = 26 (пюй 169). 3. Докажите, что если а — целое нечетное число, то аз = 1 (пюй 8). 4.
Перечислите все положительные целые числа, которые одновременно сравнимы с 5 по модулю 3 и сравнимы с 5 по модулю 2. 428 ГЛАВА 10. Некоторые специальные вопросы теории чисел 8. Докажите, что если а = 6 (пюй п1), а = 6 (пюй пз), ..., а = 6 (гаой пь), и и = НОК(им из,...,пь), то а а— а 6 (пюй и), 6. Докажите, что если ас = Ьс (шой и) и НОД(с,п) = 1, то а = 6 (шой п). 7. Докажите, что если а ь— з Ь (гпой и), то а = Ь (шой и) для всех положительных целых чисел гп. 8.
Докажите, что если а = 6 (пюй т), а =— 6 (пюй п), и НОД(т,п) = 1, то а = 6 (гаой тп). 9. Докажите, что для с ф 0 ас = Ьс (гпой п) тогда и только тогда, когда а = НОД(с, и) 10.3. КИТАЙСКАЯ ТЕОРЕМА ОБ ОСТАТКАХ В предыдущем разделе рассматривались сравнения вида ах = с (пюй т), где целые числа а и с, а также положительное целое число т были заданы, и требовалось найти целое число х, удовлетворяющее сравнению. Теперь переходим к рассмотрению системы сравнений: х = а1 (пюй тг) х = аз (шой тз) х = а„(той гп„), где числа т; — попарно взаимно простые. То есть, требуется найти целое число х, которое при делении на гп, дает остаток а„если НОД(тн т ) = 1 при г ф ~.
Еще в древние времена люди рассматривали системы сравнений и успешно их решали. Очень часто ставились задачи на устный счет, наподобие следующей. Представьте, что группа обезьян пытается разложить по кучкам груду кокосовых орехов. Если обезьяны разложат орехи в кучки по пять штук, то останется че- тыре ореха. Если разложат в кучки по четыре, останутся три ореха. Кучки по семь дадут остаток два. Кучки по девять — остаток шесть. Каково минимальное возможное число орехов? Если х — возможное число орехов в кучке, тогда наличие четырех в остатке при раскладке в кучки по пять можно выразить как х = 4 (пюй 5). Аналогично, другие условия имеют вид х в— а 3 (пюй 4); х=2 (той 7); х = 6 (той 9). Наименьшее целое положительное число х, удовлетворяющее четырем сравнени- ям, и является искомым решением.
Решение таких задач дает следующая теорема. рЛЗдЕЛ 10.3. Китайская теорема об остатках 429 ТЕОРЕМА 10.11. (Китайская творвма об остатках) Пусть ты тз, ..., т„— попарно взаимно простые числа, т.е. НОД(т;, т ) = 1 для всех т и 1, меньших или равных и, где т ф т'. Тогда система сравнений х = ат (пюа тт) х = аз (тпот) тз) х = а„(пют1 т„) Пт, М = — * тп. 3 и з — решение сравнения М зу ь— э а (тпот) т ) для каждого у, тогда решение имеет вид [ ""] »11 пат' "пь ДОКАЗАТЕЛЬСТВО.
Пусть х 1 < )т < и, определено согласно теореме. Тогда при любом к, » Му 21 т=1 »Чтт -т„ так что » » Мт. з. гпод П т, 1=1 т=1 ,У М х (пют) ть), по теореме 10.5(г) т»1 Мазь (пюс1 ть) аь (гаос) ть), поэтому х удовлетворяет и сравнениям, х = аь (гаос) ть) прн 1 < и < и. Если х' также удовлетворяет и сравнениям, тогда х — хк = 0 (тпот) тт) при 1 < т < и.
Поскольку НОД(т,, т ) = 1 при 1 ~ 1, получаем » х=х гпоппт, а=1 » т.е. решение х единственно по модулю П т;. 1=1 имеет решение, которое единственно по модулю, равному целому числу тттз т„ Далее, если 430 ГЛАВА 10. Некоторые специальные вопросы теории чисел ПРИМЕР 10.12. Найти решение системы сравнений х: — 5 (пюй 4); х = 7 (шой 11).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
