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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

20
!
.
!( )!
n
n
k
kn k
⎛⎞
=
⎜⎟
−
⎝⎠
Найдите разложение на простые множители в соответствующей сте-
пени 1000! и
1000
.
353
⎛⎞
⎜⎟
⎝⎠
4.6. Проект: степенные ряды. Для фиксированного n и заданного
простого числа p рассмотрите ряд E(n, p ) наивысших степеней p, которые
делят различные биномиальные коэффициенты
n
k
⎛⎞
⎜⎟
⎝⎠
для k = 0, 1, . . . , n. На-
пример, для n = 10 cуществуют следующие биномиальные коэффициенты:
1, 2 ⋅ 5, 3
2
⋅ 5, 2
3
⋅ 3 5, 2
3
⋅ 3 ⋅ 5, 2 ⋅ 3 ⋅ 5 . 7, 2
2
⋅ 3
2
⋅ 7. Таким образом,
E(10, 2) = {0, 1, 2}. Проверьте несколько значений n, скажем, 50; Вы заме-
тили что-либо относительно рядов Е(n, p)?
4.7. Упражнения
1. Почему формула п. 4.4 не даёт правильного ответа, когда p не явля-
ется простым числом?
2. Найдите число нулей в конце числа 1000! и в конце биномиального
коэффициента
1000
.
353
⎛⎞
⎜⎟
⎝⎠
3. Используя результат п. 4.3, покажите, что наибольшая степень про-
стого числа p, на которое делится (a + b + c)!, больше, чем наивысшая степень
числа, на которое делится a! b! c! ( для целых чисел a, b, c ≥ 1). Докажите, что
«триномиальный коэффициент»
(
)
!
!!!
abc
abc
++
является целым числом.
4. Покажите, что если p – простое число, а p
r
– делитель биномиаль-
ного коэффициента
n
k
⎛⎞
⎜⎟
⎝⎠
, тогда p
r
≤ n. [Подсказка. Степенью p, делящей би-
номиальный коэффициент, является сумма членов, первым из которых бу-
дет
⎡⎤⎡⎤⎡ ⎤
−
−−
⎢⎥⎢⎥⎢ ⎥
⎣⎦⎣⎦⎣ ⎦
nknk
pp p
. Используйте задание 4 упражнения 4.3, чтобы пока-
зать, что это либо 0, либо 1].
5. Пусть n будет составным числом, n = p
1
k1
p
2
k2
. . . p
r
kr
, где r ≥ 2. Почему
каждое простое число в степени p
r
kr
должно быть одним из чисел 1, 2, . . ., n – 1?
Докажите, что это простое число в степени является делителем (n – 1)! и, следо-
вательно, n | (n – 1)!.
Пусть теперь n будет составным числом, но r = 1, так что n представ-
ляет собой простую степень. Примем, что n > 4. Напишите формулу для
степени p, делящей (n – 1)! и покажите, что
эта степень ≥ k (достаточно для
первого члена суммы п. 4.4 быть ≥ 2, а все остальные члены должны быть
≥ 1). Докажите, что n | ( n – 1)! в этом случае тоже.

Страницы