Задача 6
Найти
остаток от деления числа
на 96.
Числа 55 и 96 взаимно просты. Поэтому
.
Найдем
Итак
.
Если
мы разделим
на
с остатком:
-,
то
.
Так что надо найти остаток от деления числа на .
Замечаем,
что число
взаимно просто с числом
,
.
Поэтому
Это означает, что
.
Итак,
нужно возвести
в степень
и найти остаток от деления этого числа
на
.
Вычислим нужный остаток, последовательно перемножая двузначные числа и находя остаток от деления произведения на .
.
Итак,
,
т.е. искомое число равно остатку от
деления числа
на число
.
Снова делаем последовательные перемножения
Следовательно,
.
Ответ:
.
Возводить
число
в степень
по модулю
можно, представив показатель
в двоичном виде:
.
Это равносильно следующему представлению
(схема Горнера)
Вычисляем,
двигаясь последовательно от самой
внутренней скобки наружу. Результат
каждого шага присваиваем переменной
.
Схема Горнера порождает следующий
алгоритм вычислений:
ЦИКЛ
ПО
ОТ
ДО
ЕСЛИ
ТО
ИНАЧЕ
КЕ
КЦ
Если вычисления ведутся по модулю , то результат каждого умножения или возведения в квадрат берется по этому модулю.
Пример.
Вычислим
.
Запишем
39 в двоичном виде
Вычисления удобно представить таблицей.
В
столбец b
сверху вниз записываем двоичные цифры
числа, начиная со старшей цифры
.
В столбце c,
двигаясь сверху по строкам, вычисляем
значение
для цифры
текущей строки. Для первой строки
(старшей цифры числа
)
по умолчанию всегда
.
b |
с |
1 |
|
0 |
|
0 |
|
1 |
|
1 |
|
1 |
|
Аналогично
возведем
:
b |
с |
1 |
|
0 |
|
1 |
|
0 |
|
1 |
|
Ответ: 55.
Комбинаторика Задача 8
Определить количество нечетных чисел, двоичная запись которых имеет 13 цифр, из которых 8 единиц. Ответ записать в виде числа сочетаний.
Решение.
Цифры
двоичного числа нули или единицы. Число
не может начинаться с 0, поэтому в старшем
разряде (самом левом) стоит 1. Число
нечетное, значит последняя его цифра
тоже 1. Осталось заполнить
разрядов так, чтобы в 6 разрядах стояли
единицы. Каждое число определяется
выбором 6 разрядов из свободных 11. Число
таких выборов равно числу сочетаний из
11 по 6:
Ответ:
.
Задача 9
Сколько существует решений уравнения
в
целых числах, где
?
Решение
Составим строку из 125 единиц и, расставив между ними запятые, сгруппируем единицы в 20 групп.
Получили
.
Чтобы сформировать 20 групп, надо
расставить 19 запятых. Запятые расставляются
в промежутках между единицами. Промежутков
124. Число способов расставить 19 запятых
на 124 местах равно числу сочетаний из
124 по 19:
.
Ответ: .
Задача 10
Сколько существует решений уравнения
в
целых числах, где
?
Решение
Сведем эту задачу к предыдущей задаче с помощью замены переменных:
.
Имеем
Получили задачу с условиями
Ответ:
.