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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

21
6. Пусть s будет нечётным, и > 1, 2
t
< s < 2
t+1
. Покажите, что
...
24
ss
+
++
s/(2
t
) < s – 1,
и докажите, что
... 1,
248
sss
s
⎡⎤ ⎡⎤ ⎡⎤
+
++<−
⎢⎥ ⎢⎥ ⎢⎥
⎣⎦ ⎣⎦ ⎣⎦
где сумма продолжается до тех пор, пока члены не станут равными нулю.
Пусть теперь n = 2
r
s, где s – нечётное число и > 1, а r ≥ 1. Покажите,
что степень 2 у делителя n! будет < n – 1. Докажите, что 2
n-1
| n!, если и
только если n является степенью числа 2.
Подобным же образом покажите, что наивысшая степень числа p, на
которое делится r!, будет менее r/(p – 1) (более правильно ≤ r – 1).
7. Предположим, что p – простое число и p
a
| (m–1). Покажите, что
p
a+b
| ((m
p
)
b
– 1) выполняется только для некоторых b ≥ 0.
8. Покажите, что
(2 )!(2 )!
!!( )!+
ab
ab a b
всегда будет целым числом.
9. Пусть n > 1. Почему степень числа 2, на которое делится n!, всегда
больше степени числа 5, на которое также делится n!? Докажите, что по-
следний ненулевой десятичный разряд n! (считая слева направо) всегда чёт-
ное число. Покажите также, что число нулей в конце (5n)! в n раз больше,
чем
число нулей в конце числа n!. (Усложнение: записывая f(n) для послед-
ней ненулевой десятичной цифры n!, покажите, что f(5n) есть последняя де-
сятичная цифра 2
n
f(n).).
4.8. Проект: функция
S(n)
Эта функция определяется как
1
()
n
d
n
Sn
d
=
⎡
⎤
=
⎢
⎥
⎣
⎦
∑
.
Напишите программу для вычисления S(n) прямо из её определения и
оцените время работы программы для значений числа n, округленно равно-
го 10 000.
Пусть теперь
[
]
ns = и q
i
= [n/i] для i = 1, 2, . . . , s. Оцените сумму
[n/d] для q
s
≤ d ≤ n. Оборвав эту сумму до [n/q
s
] + (те члены, которые нахо-
дятся в конце [n/q
s-1
]) + (те члены, которые завершают [n/q
s-2
]) + и т. д. По-
кажите, что сумма представима как
12
...
s
s
s
n
qq q sq
q
++++−
.
Докажите, что
S(n) = – s
2
+
1
2
s
d
n
d
=
⎡
⎤
⎢
⎥
⎣
⎦
∑
. (Вы можете воспользоваться
заданиями 10 и 11 упражнения 4.3). Используйте это, чтобы вычислить точ-
ные значения S(n) для n = 10
k
, где k = 5, 6, 7, 8. Оцените значение предела

Страницы