Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 79
Текст из файла (страница 79)
Поскольку числа 4 и 11 — взаимно простые, существует целое число, а именно, 10 такое, что (4)(10) = 7 (шой 11), и существует целое число (а именно, 3) такое, что (11)(3) = 5 (пюс1 4). Следовательно, (4)(10) + (11)(3) = 73, которое сравнимо с 29 по модулю 44, удовлетворяет обоим вышеприведенным сравнениям. П ПРИМЕР 10.13. Найдем ответ на вопрос об обезьянах и орехах, решая систему сравнений х=4 (шой5); х = 3 (пюс1 4); х а— а 2 (пюс1 7); х ьа 6 (той 9). Имеем М1 = 4 7.
9 = 252, Мз = 5. 7 9 = 315, Мз = 180 и Ме = 140. Поскольку числа 5 и 252 — взаимно простые, существует целое число г1 такое, что 252зз = — 4 (пюй 5) или, чтото же самое, 2х1 —= 4 (шой 5), или х1 = — 2 (шой 5). Следовательно, з1 может быть равно 7. Поскольку числа 4 и 315 — взаимно простые, существует целое число зз такое, что 315зз = 3 (пюй 4) или, что то же самое, Ззз = 3 (шой 4). Следовательно, зз может быть равно 1. Поскольку числа 7 и 180 — взаимно простые, существует целое число аз такое, что 180зз = 2 (шой 7) или, что то же самое, 5аз = 2 (пюй 7).
Следовательно, хз может быть равно 6. Поскольку числа 9 и 140 — взаимно простые, существует целое число гч такое, что 140з4 = 6 (пюй 9) или, что то же самое, 5за = 6 (шой 9). Следовательно, г4 может быть равно 3. Отсюда х = (7)(252) + (1)(315) + (6)(180) + (3)(140) (шой 5 4 ° 7 . 9) или х = 3579 (пюй 1260) и х = 1059 — наименьшее положительное целочисленное решение. П Китайскую теорему об остатках можно следующим образом обобщить на случай модулей ты тз, ..., т„, которые не являются взаимно простыми.
ТЕОРЕМА 10.14. Система сравнений х ив з а1 (пюй т1) х = аз (пюй тг) х а— а а„(пюй т„) имеет решение тогда и только тогда, когда НОД(т„т ) делит а, — а при всех 1 и 1, где 1 < 1 < т' < и. Если решение существует, оно единственно по модулю НОК(ты тз,..., т„). РАЗДЕЛ 10.3. Китайская теорема об остатках 431 ДОКАЗАТЕПЬСТВО. Для и = 1 справедливость теоремы очевидна. Покажем тех- нику доказательства, рассматривая случай и = 2.
Пусть заданы уравнения х а— а аг (шой тг); х = аг (пюй тг). Имеем х = аг + Йтг. Подставляя это значение во второе уравнение, получаем аг+йтг = аг (пюй гпг) или Ггтг = аг — аг (гной тг). Поскольку НОД(ты та) делит а1 — аг, существует решение для й, а х+Ьпг является решением для обоих уравнений. Поскольку гп, и тг делят НОК((ты гпг)), то х + йт1 + НОК((ты тпг)) также является решением. Если как хы так и хг — решения обоих сравнений, то хг — хг делится как на т,, так и на тг, и поэтому делится на НОК((тыпьг)).
Теперь предположим, что имеется система сравнений х э— з а1 (пюй тг) х = аг (шой тг) х = аь (пюй ть) х = аьч.г (пюй тьч.г) и есть значение х такое, что х = а, (пюй т,) при 1 < г < к. Поэтому каждое решение сравнения х = а; (шой т;) при 1 < г < Й имеет вид х + иМЬ где Мь = НОК(ты тг,..., ть).
Подставляя это значение в последнее сравнение, имеем х+ иМь = аьаг (пюй та+1). Если существует решение для и, тогда х+ иМь есть решение для всех й + 1 сравнений. Решение этого сравнения существует, если НОД(Мь, тьч.г) ~(х — аь.ьг). Но для всех г х — аь.ь1 = х — а, + а; — аьч.ы а посколькУ х — а; делитсЯ на т; и а; — аьч.г делитсЯ на НОД(т;,тьаю, то НОД(т„тьч.,) ((х — аь г) для всех г'. Таким образом, НОД(МЬ тьч.г) ((х — аьаг). (Чтобы убедиться в этом, подберите наивысшую степень простого числа, которая делит Мь и ть+ы Покажите, что это число делит т, и та+1 для некоторого 1.) Мы показали, что решение существует. Предоставляем читателю доказательство единственности решения по модулю НОК(гпы тпг,...,т„).
432 ГЛАВА 10. Некоторые специальные вопросы теории чисел Приведенный ниже пример демонстрирует алгоритм решения таких задач. ПРИМЕР 10.16. Найти решение: х=5 (шой6); х е— в 3 (пюй 10); х = 8 (гной 15). Решение сравнения х=5 (пюй6) с = 3 (пюй 10). Поэтому, г = 3+ 10и. Подставляя с в третье уравнение, имеем 3 + 10ц эа 8 (пюй 10).
Поэтому 10ц = 5 (шой 10) и ц = 2 (той 15). Отсюда и = 2+ 15и для некоторого и,и С = 3+ 10(2+15и) = 150и+ 23, х = 5+ 6(150и+ 23) = 203+ 6 10 15и, так что х = 203 является решением. ° УПРАЖНЕНИЯ 1. Решите а) хда сравнений; б) х= 3 (пюй4); х = — 5 (шой 9); х = 10 (пюй 35). г) х в— э 5 (пюй 7); х = 12 (пюй 15); х = 18 (пюй 22).
сравнений: б) х = 7 (шой 17); х = 9 (пюй 13); х г— а 3 (шой 12). г) х= 5 (шой9); х: — 13 (пюс1 11); х = 7 (пюй 5). приведенные ниже системы 9 (пюй 12); 6 (шой 25). в) х= а (пюс1 15); Ь (пюй 16). 2. Решите а) х= приведенные ниже системы 2 (пюй 13); 5 (гной 21). в) х=— а (пюй 15); Ь (пюй 16). имеет вид 5+6с. Подставляя эту величину во второе сравнение, получаем 5+61:— 3 (пюй 10).
Поэтому 61 = 8 (пюй 10) и РАЗДЕЛ 10.4. Свойства функции 433 3. Если в игре с разноцветными шариками в мешочке располагать их по 15 в ряд, в мешочке останутся 4 шарика. Если шарики располагать по 8 в ряд, то 3 шарика останутся в мешочке. Если каждый ряд будет содержать 23 шарика, то 10 шариков останется в мешочке. Какое наименьшее количество шариков первоначально могло находиться в мешочке? Какое было при этом количество рядов по 15, 8 и 23 шарика в каждом? 4. Предположим, имеются две шестерни: одна (шестерня А) — с 25 зубьями, другая (шестерня В) — с 54 зубьями. У шестерни А поврежден зубец, а у шестерни В повреждена секция между двумя зубцами. Шестерни сцеплены вместе, при этом шестерня А находится слева.
Шестерня А вращается по часовой стрелке, а шестерня  — против часовой стрелки. Перед началом вращения зубец шестерни А точно захвачен шестерней В, поврежденный зубец шестерни А находится за три зубца до места сцепления, а поврежденная секция — на 20 секций вперед от места сцепления. После какого количества захватов зубьев поврежденный зубец впервые попадет в поврежденную секцию? Как часто после этого поврежденные части будут вновь сталкиваться? 5.
Найдите, если это возможно, решение каждой из приведенных ниже систем сравнений: а) х = 21 (пюс) 36); в) х = 19 (пюсс 49); х = 5 (пюс1 8). х = 10 (пюс) 14). б) х = 8 (пюс) 12); х = 5 (апой 9); х: — 14 (шос) 15). 21=3 7 22 = 2 . 11 23 = 23 24 2з 3 25 = 5г 26 = 2 13 27 = Зз 28 2г 7 29 = 29 30= 2.3.5 31 = 31 32 = 2з 33 = 3.11 34=2 17 35 = 5.7 36 =2г Зг ЗТ= 37 38 = 2.19 39=3 13 40 2з 5 11 = 11 12 =2г 3 13 = 13 14 = 2.7 15=3 5 16 = 24 17 = 17 18=2.3г 19 = 19 20 2г 5 1=1 2=2 3=3 4 = 2г 5=5 6=2.3 7=7 8 = 2з 9 Зг 10=2 5 Каждое из целых чисел, выделенных жирным шрифтом, не делится ни на 2, ни на 10.4. СВОЙСТВА ФУНКЦИИ ф Пусть и = р,'р ' р„" — разложение на простые множители числа и.
Каждый положительный делитель числа п либо равен 1, либо делится на р, при некотором с, и каждое целое число, взаимно простое с и, не имеет ни одного из указанных чисел в качестве делителя. Некоторые свойства числа п зависят от количества целых чисел з, 1 < з < п, не содержащих ни одно из р; в качестве делителя. Например, если п = 40 = 2з 5, тогда целые числа в, 1 < з < и, и их разложения на множители имеют вид 434 ГпдВА 10. некоторые специальные вопросы теории чисел 5, и является числом, взаимно простым с и = 40.
Количество чисел е, 1 < е < и, взаимно простых с и, обозначается ф(40) = 16. ОПРЕДЕЛЕНИЕ 10.16. Пусть ф(п) — количество положительных целых чисел, меньших и и взаимно простых с п, т.е, ф(п) — количество приведенных вы- четов по модулю п. Функция ф называется тотиент-функцией Эйлера, или функцией Эйлера ф. Из приведенной выше таблицы разложения на множители следует, что Ф(1) = 1; ф(2) = 1; ф(3) = 2; ф(4) = 2; ф(5) = 4; ф(6) = 2; ф(7) = 6; ф(8) = 4; ф(9) = 6; ф(10) = 4; ф(11) = 10; ф(12) = 4.
Любое положительное целое число п может быть выражено с помощью положительных целых чисел, не превосходящих и взаимно простых с каждым делителем числа п. Например, 6 = 2. 3 имеет четыре делителя: 1, 2, 3 и 6. Из приведенной выше таблицы следует, что ф(1) + ф(2) + ф(3) + ф(6) = 1 + 1 + 2 + 2 = 6. Это свойство сформулировано в следующей теореме. ТЕОРЕМА 10.17. (Гаусс) Если п — положительное целое число, то ф(й) = п, а(п Для иллюстрации доказательства теоремы 1ОД7 в частном случае д = 1, 2, 3, 4, 6 и 12 находим, что соответствующие значения п/й равны, соответственно, п/й = 12, 6, 4, 3, 2 и 1, так что две упомянутые суммы равны.
С) где делители й являются положительными делителями числа п. ДОКАЗАТЕЛЬСТВО. Пусть й — положительный делитель числа п. Пусть С(й)— множество положительных целых чисел 1 < т < п, для которых НОД(т, п) = й. С(й) и С(й') не пересекаются, если й ф й', поскольку произвольное целое число может иметь с числом и только один наибольший общий делитель. Согласно теореме 7.8, С(й) является также множеством положительных целых чисел т, 1 < т < и, для которых НОД(ги/й,и/й) = 1.
Но количество положительных целых чисел, меньших п/й и взаимно простых с п/й, совпадает со значением функции ф(и/й). Поскольку объединение этих множеств есть множество целых чисел между 1 и п, то и = ,'Г,„~„ф(п/й). Но для каждого й, которое делит п, имеется соответствующее п/й, которое делит и. Следовательно, ~а~„ ф(п/й) = 2 а~„ ф(й) = и, что и доказывает теоРемУ.
ПРИМЕР 10.18. Пусть п = 12. Делителями 12 являются 1, 2, 3, 4, 6 и 12. Согласно приведенной выше таблице значений функции Эйлера ф ф(1) + ф(2) + ф(3) + ф(4) + ф(6) + ф(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12. РАЭДЕЛ 10.4 Свойства функции 435 Теперь перейдем к способам вычисления ф(п) для любого целого положительного числа и. Решить указанную задачу помогут три следующие теоремы. ТЕОРЕМА 10.19. Если числа т и и — взаимно простые, то ф(тип) = ф(т)ф(п). ДОКАЗАТЕЛЬСТВО. Пусть числа т и и — взаимно простые. Целое число является взаимно простым с тп, тогда и только тогда, когда оно взаимно простое и с т, и с и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
