Материал: LS-Sb89586
Внекоторых случаях вычисляют c/a в кольце вычетов по модулю b.
Вэтом случае сначала можно вычислить 1/a, затем умножить результат на c в кольце вычетов по модулю b.
Уточняем, что умножить число в кольце вычетов по модулю b означает сначала умножить число, затем заменить результат его остатком от деления на b.
Пример. Можно решить уравнение 7x = 1 в кольце вычетов по модулю 9, то есть провести вычисление 1/7 в Z9 .
Вданном случае обозначим неизвестную величину как х. Тогда
x= 1/7 в Z9
7x 1 (mod 9)
7x – 1 9
7x – 1 = 9y
7x – 9y = 1
Получаем уже знакомую ситуацию – линейное диофантово уравнение. Можем его решить, но для первоначальной задачи достаточно найти всего одно значение х – например, подойдет x = 4. Заметим, что это число находится в пределах от 0 до 8, и поэтому может быть остатком при делении на 9.
Итак, ответ: x = 4.
Примечание. Ответ легко проверить умножением: 4 7 при делении на 9 дает остаток 1.
Если бы искали, например, 5/7 в Z9 , то сначала нашли бы 1/7 в Z9 (по-
лучив число 4), а затем домножили бы это число на 5 и взяли бы остаток при делении на 9 (остаток от деления 20 на 9 равен 2).
В этом случае ответ был бы равен 2.
Примечание. В задачах на нахождение выражений вида a/b в кольце вычетов по модулю c ответ всегда единственный, и является целым числом, находящимся в пределах от 0 до (c – 1).
В некоторых случаях деление невозможно, поскольку не каждое диофантово уравнение имеет решение. Например, уравнение 4x 1 (mod 10) не имеет решений, поскольку 4x – четное число, и при делении на 10 остаток будет четным.
11
1.18. Китайская теорема об остатках
Пусть m1, m2, ...,mn – попарно взаимно простые модули (то есть каждые два взаимно просты между собой), r1, r2, ...,rn – остатки. Тогда существует такой x, что
x r1(mod m1); |
|
||
|
|
... |
|
|
|
|
|
x r (mod m ). |
|
||
|
n |
n |
|
Вообще говоря, такой x не единственный, поскольку от прибавления к |
|||
нему величины m1m2...mn остатки по модулю останутся теми же. |
|
||
Но если поставить дополнительное условие 0 x m1m2...mn , |
то такой x |
||
существует, и он единственный. |
|
|
|
Примечание. То, что модули попарно взаимно просты – существенная |
|||
деталь. Например, предположим, |
что m1 2, m2 4, r1 1, r2 |
2. Тогда |
|
искомое число должно быть одновременно и четным, и нечетным, что невозможно.
Сначала, для примера, предположим, что у нас два модуля: m1 4,
m2 7, r1 1, r2 3.
Тогда представим искомое число в виде суммы двух чисел: одно дает остаток 1 при делении на 4 и кратно 7, а другое дает остаток 3 при делении на 7 и кратно 4.
Тогда сумма этих чисел даст искомые остатки.
В качестве первого числа можем взять 21, в качестве второго – 24. Сложив эти числа, получим 45.
Поскольку для единственности решения поставлено условие 0 x m1m2 ,
заменим число 45 его остатком от деления на 28, то есть числом 17.
Можно проверить, что оно действительно дает указанные остатки при делении на 4 и на 7.
Теперь – построение решения для китайской теоремы об остатках в общем виде.
Здесь будем строить его похожим образом, то есть в виде суммы n слагаемых, каждое из которых дает требуемый остаток по своему модулю, и при этом делится на остальные модули.
12
Первое слагаемое обеспечит остаток по первому модулю, второе – по второму, и так далее.
Обозначим сi m1m2...mn . mi
Из условия теоремы вытекает, что НОД (сi ,mi ) 1.
Следовательно, для каждого i существует di такое, что cidi 1(mod mi ). Найти такое di можно, если решить сравнение dici bimi 1(modmi ) (иначе говоря, найти частное решение диофантова уравнения).
Итак, для каждого i |
выполнено условие cidi 1(mod mi ). Поэтому |
cidiri ri (modmi ). |
|
Число x c1d1r1 c2d2r2 |
... cndnrn (modm1m2...mn ) – искомое. Имеется в |
виду, что будет взят остаток от деления данного числа на произведение m1m2...mn .
В самом деле, это число:
дает остаток r1 при делении на m1 (поскольку первое слагаемое дает указанный остаток, а остальные слагаемые делятся на m1),
дает остаток r2 при делении на m2 (поскольку первое слагаемое дает указанный остаток, а остальные слагаемые делятся на m2), и так далее.
1.19.Непрерывные дроби
иперевод рационального числа в конечную дробь
Определение. Непрерывной дробью называют дробь вида
a0 |
|
|
1 |
|
|
|
|
a0 , ak N , k 0. |
|
1 |
|
|
|
||||
|
a1 |
|
|
|
|
|
|
|
a2 |
|
|
1 |
|
|
|
||
|
|
a3 |
... |
|||||
|
|
|
|
|||||
Если эта дробь где-либо заканчивается, ее называют конечной непрерывной дробью. Конечные непрерывные дроби соответствуют рациональным числам.
Пример. 4 |
|
1 |
|
4 |
|
|
1 |
|
4 |
|
5 |
|
4 |
|
5 |
. |
|
|
1 |
|
11 |
|
11 |
|
|||||||||
2 |
|
|
|
|
|
11 |
||||||||||
5 |
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Возможно и обратное действие: получение непрерывной дроби из рационального числа:
13
21 |
2 |
5 |
2 |
|
1 |
|
2 |
1 |
|
2 |
1 |
|
|
|
2 |
|
|
|
1 |
|
|
2 |
|
|
|
1 |
|
|
|
. |
|||
8 |
8 |
|
8 |
|
1 |
3 |
1 |
|
1 |
|
|
1 |
|
1 |
|
|
1 |
|
1 |
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
5 |
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
5 |
|
2 |
|
|
1 |
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
1 |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
3 |
|
|
|
|
|
|
|
1 |
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|||
Обычно такую непрерывную дробь записывают в виде (2; 1, 1, 1, 2). Целая часть отделяется точкой с запятой.
Теперь покажем другой способ нахождения коэффициентов непрерывной дроби. Применим алгоритм Евклида к числам 21 и 8:
21 = 8 ∙ 2 + 5;
8 = 5 ∙ 1 + 3;
5 = 3 ∙ 1 + 2;
3 = 2 ∙ 1 + 1;
2 = 1 ∙ 2.
Обратите внимание на связь коэффициентов непрерывной дроби с неполными частными в алгоритме Евклида.
2.КОМБИНАТОРИКА
2.1.Задачи комбинаторики
1.Найти количество объектов, удовлетворяющих некоторым условиям.
2.Занумеровать элементы и построить алгоритм нахождения элемента по номеру и номера по элементу.
2.2.Правило произведения
Если А содержит n элементов, множество В содержит m элементов, то множество пар вида ai , b j , где ai А, b j B, содержит mn элементов.
Пример 1. Сколько существует способов поставить две шахматные ладьи на доску 8 8 так, чтобы они не «били» друг друга?
Решение. Есть 64 способа поставить первую ладью, и на каждый из них приходится по 49 способов поставить вторую ладью (поскольку первая ладья занимает одну клетку, и бьет при этом 14 клеток, то остается 49 клеток для второй ладьи). Таким образом, получим 64 49 вариантов расстановки двух ладей.
14
Но при этом каждая расстановка при таком подсчете будет сосчитана дважды, поскольку можно начать с первой ладьи, а можно – со второй. Поэтому найденное количество нужно разделить на 2.
Ответ равен (64 49)
2 1568.
Ответ. 1568.
Пример 2. Сколько существует трехзначных чисел, у которых все цифры различны?
Решение. Для первой цифры существует 9 вариантов, от 1 до 9. Когда ее выбрали, для второй цифры – тоже 9 вариантов, поскольку она не должна совпасть с первой. Когда выбрали первые две цифры, то для третьей осталось 8 вариантов.
По правилу произведения получим ответ: 9 9 8 648.
Ответ: 648.
2.3. Правило сложения
Идея рассуждения – разбить все варианты на группы, каждая из которых состоит из «одинаково устроенных» комбинаций.
Пример. Сколько существует способов поставить двух шахматных королей на доску 8 8 так, чтобы они не «били» друг друга?
Решение. В данном случае количество полей, которое «бьет» король, зависит от его положения на доске.
Если он в углу (4 варианта), то для второго короля свободны 60 полей, если у края доски (24 варианта), то свободны 58 полей, а если отстоит не в углу и не у края (36 вариантов), то свободны 55 полей.
Таким образом, получим 4 60 + 24 58 + 36 55 = 3612. Разделив это количество пополам (по той же причине, что в примере 1), получим 1806.
2.4. Перестановки
Перестановкой называют упорядоченный набор чисел 1, 2, 3, … n, возможно, переставленных в другом порядке – например, 3, 2, 1, 4, 5, 6, …, n.
Первый элемент перестановки можно выбрать n способами, тогда второй останется (n – 1) способ, на третий – (n – 2) способа, и так далее до заключительного элемента, для которого останется ровно один вариант.
Таким образом, количество перестановок равно n(n – 1)(n – 2) … 2 1 = n!
15