Элементы теории чисел и криптозащита. Воронков Б.Н - 19 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

19
Общий принцип тот же самый для любых p и n. Так как n! = 2 ⋅ 3 ⋅ 4, . . . ,
n и p – простое число, попробуем сосчитать, сколько раз p входит
в сомножители 2 ⋅ 3 ⋅ 4, . . . , n числа n!. Чтобы проделать это, мы начнём с вы-
числения числа сомножителей p среди 2 ⋅ 3 ⋅ 4, . . . , n . Затем мы вычислим
сомножители вида p
2
, каждый из которых даёт дополнительный множитель p
в n!. Далее мы должны вычислить сомножители p
3
, каждый из которых даёт
сомножитель p в n!, дополнительный к тем, которые уже были перечислены,
и т. д. Сомножители положительного числа k среди 2 ⋅ 3 ⋅ 4, . . , n будут k, 2k,
3k ,. . . ,[n/k]k , следовательно, их число равно [n/k]. Таким образом, количество
сомножителей вида p будет [n/p], вида p
2
– [n/p
2
] и т. д. Окончательный ре-
зультат сформулируем следующим образом:
Степень простого числа p, которое является делителем n!, есть
...,
⎡⎤⎡ ⎤⎡ ⎤
++ +
⎢⎥⎢ ⎥⎢ ⎥
⎣⎦⎣ ⎦⎣ ⎦
nn n
pppppp
где суммирование продолжается до тех пор, пока
члены не станут равными 0, т. е. до тех пор, пока p
r
> n.
Читатель может попробовать доказать следующий эквивалентный вид
полученного результата: степень p, делящего n!, есть (n – s)/(p – 1), где s яв-
ляется суммой цифр n, когда оно выражено по основанию p. (Т. е., если n =
t
i0
a
=
=
∑
i
p
i
, где 0 ≤ a
i
< p для всех i, тогда s =
∑
=
t
i
a
0
i
).
Например, пусть n = 100 и p = 2. Степенью 2, делящей 100!, тогда будет
такое число
100 100 100 100 100 100
248163264
⎡⎤⎡⎤⎡⎤⎡⎤⎡⎤⎡⎤
+++++
⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥
⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦⎣⎦
= 50 + 25 + 12 + 6 + 3 + 1 =
= 97. Точно так же, если n = 100 и p = 5, тогда степенью 5, делящего 100!, будет
число
100
5
100
25
⎡
⎣
⎢
⎤
⎦
⎥
+
⎡
⎣
⎢
⎤
⎦
⎥
=
20 + 4 = 24. Таким образом, 100! = 2
97
· 5
24
и ещё надо ум-
ножить на другие простые сомножители в соответствующих степенях (вклю-
чая, конечно, степени числа 3 и т. д.). Отметим, что наибольшей степенью чис-
ла 10, на которое делится 100! будет 24; следовательно, в десятичном выраже-
нии число 100! содержит 24 нуля, а в двоичном – их было бы 97.
4.5. Компьютерные упражнения
1. Напишите (короткую!) программу вычисления чисел по формуле
(
)
1n
⎡⎤
+
⎣⎦
2
– n для n = 1, 2, 3 . . . , 100. Теперь объясните, что делает про-
грамма. (Подсказка: если (m – 1)
2
≤ n < m
2
, то, что такое
[
]
n ?).
2. Напишите программу, которая использует результат п. 4.4 для вы-
числения степеней простого числа p, которое является делителем n! для за-
данных p и n. Используйте это также для того, чтобы вычислить степени p,
которые будут делителями биномиального коэффициента

Страницы