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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

66
Действительно (более трудное упражнение),
φ
(n) никогда не принимает
значений 2 ⋅ 7
k
, k ≥ 1. См. ниже, п. 18.13).
2. Найдите разложение по степеням простых чисел 10! и, отсюда,
найдите
φ
(10!).
3. Покажите, что для некоторого n > 2
φ
(n) является чётным. [Под-
сказка. Либо n = 2
k
для некоторого k > 1, или p | n для некоторого нечётного
простого числа р. Это также можно обнаружить, заметив, что для n > 2,
числа х взаимно простые с n и, удовлетворяя 1 ≤ x ≤ n, могут быть поделены
на пары {x, n – x} различных чисел].
4. Представив n = 2
k
r, где r – нечётное число, покажите, что если
φ
(n) = n/2, то n является степенью 2.
5. Используйте формулу для
φ
(n), чтобы описать все n, для которых
φ
(n) является кратным 4. (Например, если 8 | n, тогда 4 |
φ
(n)).
6. Предположим, что n – составное число. Покажите, что
φ
(n) ≤ n –
n
.
[Подсказка. Если n – составное число, тогда оно имеет простой сомножи-
тель р ≤
n
. Какое число, кратное р, будет ≤ n ?].
7.* Покажите, что, если
φ
(n) = 2 ⋅ 3
6k+1
, где k ≥ 2, тогда n = 3
6k+2
или n =
= 2 ⋅ 3
6k+2
. [Достаточно трудно проверить, что для этих значений n,
φ
(n) име-
ет установившееся значение. Этот сложный случай следует показать путем
преобразований]. Как следует из этого, существует бесконечно много зна-
чений у, для которых уравнение
φ
(х) = у имеет точно два решения для х.
Что удивительно, неизвестно, существуют ли какие-нибудь значения у, для
которых
φ
(х) = у имеет точно одно решение для х.
8. Проверьте, что, если n = 1 или n = 2
i
, или n = 2
i
3
j
для целых чисел
i ≥ 1, j ≥ 1, тогда
φ
(n) является делителем n.
9. Это модификация п. 8, и она несколько сложнее. Действительно,
примем
φ
(n) | n и n > 1. Пусть Р будет произведением всех различных про-
стых чисел р, делящих n, а Q будет произведением сомножителей р – 1 для
всех таких р. Покажите, что Q | P, и докажите, что Q не делится ни на какой
квадрат > 1 и что Р может быть только произведением одного или двух
простых чисел. Выведите из этого, что нет простых чисел р > 3, которые
могли бы быть сомножителями Р и, отсюда, что в действительности n имеет
одно значение, приведённое выше, в задании (8).
10. В противоположность п. 18.3 покажите, что если m | n, тогда
φ
(тn) = m
φ
(n). (Используйте п. 18.4).
11. Покажите, что если n – нечётное число и
φ
(n) = 2
r
для некоторого
r ≥ 1, тогда n должно быть произведением различных простых чисел. Ис-
пользуя тот факт, что 2
32
+ 1 не является простым числом, покажите, что не
существует нечётного числа n, для которого
φ
(n) = 2
32
. С другой стороны,
для 1 ≤ r ≤ 31 должны существовать нечётные числа n, для которых
φ
(n) = 2
r
. Что представляют собой чётные числа n, для которых
φ
(n) = 2
32
?

Страницы