Дискретно-непрерывная математика (стр. 29 )

Нам остается это сравнение сократить на 1∙2 . ...(p-1).

63. Будем искать т в видеТогда

Стоящее cлева произведение должно делиться на 5. Значит, либо одно из чисел р1, р2,....,рk есть 5 (пусть для определенности р1 = 5), либо на 5 делится одна из разностей р1 — 1, р2—1, …, рk — 1 (пусть в этом случае (p1 —1) 5). В первом из этих случаев р1 —1=4, чего не может быть, так как 10 на 4 не делится. Второй случай, поскольку р1 должно быть простым числом и 10 (p1 — 1), возможен лишь при р1 = 11. Но тогда α1 = 1, и из теоремы 25 следует, что

т. е. либо либо

В итоге мы имеем m1 = 11, m2 = 22.

Если т нечетное, то (ибо правая часть написанного равенства есть степень двойки):

Это возможно лишь при k = 2, р1 = 3, р2 = 5, т. е. при т = 15.

Пусть теперь число т — четное. Положим для определенности р1=2. Очевидно, по-прежнему и мы имеем

Очевидно, α≤4. Если α = 1, то случай подобен рас­смотренному: написанное неравенство возможно так­же лишь при k =3, p2 = 3, р3 = 5, т. е. при т = 30.

Если α = 2, то k = 2, р3 = 5 и m = 20.

Если α = 3, то k = 2, р2 = 3 и m = 24.

Если, наконец, α = 4, то k = 1 и т = 16.

Итак, решения нашей задачи: m1= 15, m2 = 30, т3 = 20, т4 = 24, т5 = 16.

64. Предположим, что

Каждое из чисел вида pi— 1 есть либо единица, либо четное число, и потому не может быть семеркой. Будучи на единицу меньше простого числа, оно не мо­жет равняться 14. Значит, семеркой является одно из чисел Но тогда pi — 1 =6, а 14 на 6 не делится.

65. Пусть Рассмотрим сначала случай, когда т есть степень простого числа: т = рα. Для того чтобы некоторое число было взаимно простым с т, необходимо и достаточно, чтобы оно не делилось на р. Но среди чисел 0, 1, 2, ..., т—1 имеется всего делящихся на р чисел. Следовательно, взаимно простых с р чисел в этом списке имеется столько:

Заметим теперь, что для взаимной простоты а и т необходимо и достаточно, чтобы с а был взаимно прост остаток от деления а на т.

По только что установленному число остатков от деления на взаимно простых с равно Но, как было выяснено в процессе решения задачи 28, из равноостаточности чисел при делении на все следует их равноостаточность при делении на т, и наоборот. Кроме того, для взаимной простоты не­которого числа с т необходимо и достаточно, чтобы оно было взаимно просто с каждым из чисел

Следовательно, каждой комбинации остатков от деления на взаимно простых с соответствующими делителями, соответствует ровно один остаток от деления на т, взаимно простой с т. Нам остается заметить, что число таких комбинаций ос­татков равно

66. Мы имеем

Поэтому

Здесь по теореме Эйлера первое слагаемое при де­лении на т1m2 равноостаточно с А, а второе делится на т1m2. Значит, вся сумма при делении на т1m2 равноостаточна с А.

67. Предоставляется читателю.

68. Предоставляется читателю.

69. Предоставляется читателю.

70. п13 — п = n(n12— 1). Но

Поэтому либо п р, либо (п12— 1) р для р = 2, 3, 5, 7, 13. Остается сослаться на теорему 16.

71. Предоставляется читателю.

72. Предоставляется читателю.

73. Пусть наибольший общий делитель чисел а и b есть d. Если с не делится на d, то уравнение

в целых числах неразрешимо. Если же с делится на d, то обе части уравнения можно сократить на d, и мы подходим к уже рассмотренному случаю.

74. Пусть А и В таковы, что

Положим

Тогда

и (xt,yt) действительно является решением нашего уравнения.

Поскольку свободные члены и коэффициенты при t в выражениях для xt и yt, так сказать, «примерно пропорциональны», мы можем надеяться получить представления наших решений в меньших числах.

В самом деле, мы можем написать:

или, полагая

мы получаем

Заметим, что способ решения уравнений в целых числах, приведенный в задаче 74, позволяет обхо­диться меньшими числами, хотя и требует несколько более сложных вычислений.

б) Воспользуемся тем, что 25 по модулю 13 при­надлежит показаМы можем написать:

или, после упрощений,

76. Условие в) обеспечивается автоматически, а условие г) следует из теоремы 25.

78. Предоставляется читателю.

79. Предоставляется читателю.

80. а) 8φ(21)-1 = 811 = 645∙8. При делении на 21 это число равноостаточно с 8. Значит, числа 8а + b и а+ 8b равноделимы на 21.

б) 12φ(31)-1=1229=(122)14∙12 = 14414∙12 при де­лении на 31 равноостаточно с 1114• 12 = 1217 ∙12 = (—3)7∙12 = — (33)2∙3∙12 = —(31 — 4)2(31 + 5), что равноостаточно с —16∙5 = —80. Последнее чис­ло очевидно равноостаточно с 13. Значит, числа 12а + b и a +13b равноделимы на 31.

Модуль 5

Элементы комбинаторики

Комбинаторика — один из разделов дискретной математики, которая имеет важное значение в связи с использованием ее в теории вероятностей, математической логике, теории чисел, вычислительной технике, кибернетике. Цель этого модуля — ознакомить читателей с основными понятиями комбинаторики и методами решения комбинаторных задач. При изучении комбинаторики мы считали целесообразным систематически использовать понятие множества и операций над множествами, поскольку большинство задач комбинаторики можно сформулировать как задачи теории конечных множеств.

При решении комбинаторных задач нужно особое внимание обратить на метод производящих функций и метод траекторий. Эти методы важны сами по себе, так как находят широкое применение не только в комбинаторике, но и во многих разделах современной математики.

Микромодуль 16

Основные принципы комбинаторики

5.1. Введение