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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

22
lim
n
→∞
()
ln( ) .
⎛⎞
−
⎜⎟
⎝⎠
Sn
n
n
5*. Дополнение
5.1. Постоянные Капрекара. Пусть b будет положительным целым
(основанием) и пусть a будет положительным целым с разложением в виде
четырёх цифр в базисе b (например, b = 10, a = 2674), чтобы не все цифры
были бы одинаковыми. Определим T(a) = a′ – a′′, где a′ (соответственно, а′′)
есть целое число, представленное по основанию b, полученное
записью
цифр в порядке уменьшения (соответственно, возрастания). (Например,
b = 10, a = 2674, a′ = 7642, a′′ = 2467, T(a) = 5175). Для b = 10 покажите, что
T(a) = a, если и только если a = 6174. Начните с рассмотрения главного че-
тырёхразрядного числа pqrs (это десятичные цифры), для которых
p ≥ q > r ≥ s, и покажите, что вычитание srqp
даёт разность, крайние цифры
которой дают в сумме 10, а средние цифры дают в сумме 8. Похожий ре-
зультат получается, когда q = r. Это означает, что возможности для T(a)
очень ограничены.
Число 6174 называется постоянной Капрекара по основанию 10. Для
основания b = 5 найдите единственное a, для которого T(a) = a: оно называ-
ется постоянной
Капрекара по основанию 5. Покажите, что в обоих случаях
для некоторого начального значения a последовательность T(a), T
2
(a) =
= T(T(a)), T
3
(a) = T(T
2
(a)), . . . достигает постоянной Капрекара по этому ос-
нованию. (Для b = 10 рассмотрите ограниченный ряд чисел, который равен
T(a), найденный выше).
Напишите программу повторения оператора T для некоторого вы-
бранного b (конечно, ограниченного b ≤ 10) и затем найдите постоянную
Капрекара по основанию b, если она существует.
5.2. Простые числа Гильберта. Пусть H = {4k + 1: k = 0, 1, 2, 3, . . .}.
Покажите, что H замкнуто для умножения (т. е., если a ∈ H и b ∈ H, тогда
ab ∈ H). Целое число h ∈ H называется простым числом Гильберта, если
всякий раз, когда h ∈ H для a и b ∈ H, либо a = 1, либо b = 1. Напишите про
-
грамму нахождения простых чисел Гильберта. Найдите целые числа, кото-
рые умножаются в двух разных направлениях как произведения простых чи-
сел Гильберта.
5.3. Ряды Фарея. Напишите программу нахождения дробей Фарея
порядка n, т. е., дробей p/q в наименьших членах (т. е., p и q взаимно про-
стые) таких, чтобы знаменатель q ≤ n и (здесь ловушка) дроби были бы упо-
рядочены в возрастающем порядке значений. Существует алгоритм для пе-
рехода от дробей Фарея порядка
n к дробям порядка n + 1: между каждой

Страницы