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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

68
Определите единственные значения n, при которых n
φ
(n) имеет сле-
дующие значения: 20, 12, 42, 40, 500, 1000, 10 100, 100 000, 9 003 000.
18.9. Проект. Напишите программу, которая для заданного целого
числа k > 0 либо показывает, что отсутствует число n, для которого
n
φ
(n) = k, либо найдётся единственное n с таким свойством, используя
п. 18.8. Таким образом, Вы начнёте с нахождения наибольшего простого
делителя р у k, и, определения наивысшей степени р числа, делящего k. Ес-
ли степень будет чётной, тогда Вы докажете, что такого числа n не сущест-
вует. Если степень будет p
2r–1
, тогда Вы обратите внимание на делитель в n
и замените k на k/p
r
φ
( p
r
). Конечно, если последнее не является целым чис-
лом, то такого n не существует.
18.10. Проект. Неизвестно, существует ли бесконечно много n, для
которых
φ
(n) =
φ
(n + 1). Найдите все значения n < 10 000, для которых это
выполняется. Найдите также значения n < 10 000, для которых
φ
(n) =
=
φ
(n + 3). (Их существует достаточно мало!).
18.11. Проект: повторное применение функции Эйлера. Покажите,
что, последовательность, образованная из n,
φ
(n),
φ
2
(n) =
φ
(
φ
(n)),
φ
3
(n) =
φ
(
φ
(
φ
(n))), . . . , в конце концов становится равной 2. Для n > 2 пусть
классом C(n) из n будет значение k, для которого
φ
k
(n) = 2. Вычислите точ-
ное значение С(2
r
) и С(2 ⋅ 3
r
). Теперь, для заданного значения k требуется
найти наименьшее значение n, которое имеет класс k. Напишите программу
для иллюстрации того, что для k = 1, 2, 3, 4, 5, 6 наименьшими n будут (со-
ответственно) n = 3, 5, 11, 17, 41, 83. Как продолжить последовательность
малых n? Содержит ли она только простые числа? Несколько расширим
знания о свойствах этого класса с помощью следующих упражнений.
18.12. Упражнения: некоторые свойства класса C(n)
Некоторые из них сделаны на основе наблюдения, что, пока
φ
(mn) =
=
φ
(m)
φ
(n), когда (m, n) = 1, мы получим
φ
(mn) = m
φ
(n), когда m | n. Вспом-
ните, что также
φ
(n) является чётной для n > 2 (см. выше, п. 18.5 (3)). Мы
примем n > 2.
1. Когда n – нечётное и (2, n) = 1, мы получим
φ
(2n) =
φ
(n). Докажите,
что
φ
k
(2n) =
φ
k
(n) для всех k и, следовательно, C(2 n) = C(n).
2. Когда n – чётное, и 2 | n, мы получим
φ
(2n) = 2
φ
(n), и, так как
φ
k
(n)
является чётным, мы получим
φ
2
(n) = 2
φ
2
(n). Докажите, что
φ
k
(2n) = 2
φ
k
(n),
если
φ
k–1
(n) является чётным и, отсюда, k ≤ C(n). Докажите, что
φ
С(n)
(2n) = 4, а C(2n) = C(n) + 1.

Страницы