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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

18
13. Покажите, что для n – положительного числа
2
5
n
⎛⎞
+
⎜⎟
⎝⎠
2
< n(n + 1) <
1
2
n
⎛⎞
+
⎜⎟
⎝⎠
2
,
7
10
n
⎛⎞
+
⎜⎟
⎝⎠
2
< n(n + 2) < (n + 1)
2
и
7
10
n
⎛⎞
+
⎜⎟
⎝⎠
2
< (n + 1)(n + 2) <
3
2
n
⎛⎞
+
⎜⎟
⎝⎠
2
.
Докажите, что
1298nn n n
⎡⎤⎡⎤
++++= +
⎣⎦⎣⎦
.
14. Пусть n – целое число ≥ 1 и s =
n
⎡
⎤
⎣
⎦
. Покажите, что s
2
≤ n ≤ s
2
+ 2s
и
22
22
1, ,
1
,2
ssnss
n
s
sssnss
⎧
−≤<+
⎪
⎡⎤
=
⎨
⎢⎥
+
⎣⎦ +≤≤+
⎪
⎩
.
22
22
2
,,
1, 2 ,
2, .
ssnss
n
s
ssns s
s
sssn
⎧
≤< +
⎪
⎡⎤
=+ +≤<+
⎨
⎢⎥
⎣⎦
⎪
++=
⎩
В особенности покажите, что [n/s] = s + 2 только в случае, если n + 1
является полным квадратом.
15. Предположим, что i
2
≤ n (i > 0). Докажите, что
[]
/
n
i
ni
⎡
⎤
=
⎢
⎥
⎣
⎦
.
(Одним из вариантов доказательства будет начало с представления
n = ai + b, где 0 ≤ b < i. В этом случае вы должны показать, что a > b. Пола-
гая a ≤ b, докажите, что i ≥ a + 1, и тогда, используя n < (a + 1)i, выведите
противоречие). Далее покажите, что если [n/u] = u и [n
/(i + 1)] = v (и про-
должая полагать i
2
≤ n), тогда [n/w] = i для всех w c условием
v + 1 ≤ w ≤ u.
4.4. Степень простого числа, делящего n!
Пусть n ≥ 2, а p будет простым числом. Мы желаем найти точную
степень p, которая делит n!. Например, если n = 6, тогда n! =
=
23456 720⋅⋅⋅⋅=
; для p = 2 ответом будет 4, для p = 3 это будет 2 и для p =
= 5 это будет 1, в то время как для другого простого числа ответом будет 0.
Заметим, что для p = 2, скажем, множителями среди 2, 3, 4, 5, 6, которые
делятся на 2, будут 2, 4, 6. Но мы должны считать 4 большее число раз, так
как оно делится на 2
2
, а не только точно на 2. Таким образом, общая степень
будет 3 + 1, 3 получается из 2, 4, 6 и одна дополнительная 1 исходит от 4.

Страницы