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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

17
a
a
b
bbb
⎡⎤
⎢⎥
⎡
⎤
=
⎢⎥
⎢
⎥
⎣
⎦
⎢⎥
⎣⎦
.
9.* Докажите следующее красивое обобщение задания 8 упражнения
4.3. Предположим, что
f – непрерывная, неубывающая функция, обладающая
тем свойством, что для всех
x из области определения f, если f(x) является це-
лым числом, то
x тоже целое. Тогда (принимая f непрерывной на отрезке {y: [x
]
≤ y ≤ x}) получим [f([x])] = [f(x)]. (Подсказка. Пусть n = [x] и предположим,
что
n < x. Покажите, что [f([n])] ≤ [f(x)], предполагая первоначально обратное,
так что [
f([n])] + 1 ≤ [f(x)]. Докажите, что f(n) < < [f(x)] ≤ f(x) и используйте
свойство непрерывности, чтобы показать, что существует
y такой, что n < y ≤ x
и
f(y) = [f(x)]. Так как y должен быть целым числом (из допущений относи-
тельно
f), то полученный результат является противоречием).
10. Пусть
r и i будут целыми числами, а i > 0. Пусть
2
ri
x
i
+
=
. Исполь-
зуйте [
x] ≤ x, чтобы показать, что 2[x] – 1 <
r
i
+ 1
, и используйте неравенство
x – 1 < [x], чтобы показать, что r – 1 ≤ 2[x] + 1. Докажите, что
i
r 1+
≤ 2[x] + 1 и 2[x] – 1 <
i
r 1
+
, а отсюда наименьшим нечётным числом ≥
i
r 1+
будет 2
⎥
⎦
⎤
⎢
⎣
⎡
+
i
ir
2
+ 1. При каких условиях вышеприведенным нечетным
числом будет 1?
11. Пусть
x > 0. Покажите, что число нечётных чисел ≥ 1 и ≤ x будет
[(
x + 1)/2].
12. Пусть
k будет целым числом ≥ 2. Разделите 3
k
на 2
k
: 3
k
= = q × 2
k
+ r,
где 0
≤ r < 2
k
, так что q = [3
k
/2
k
]. Пусть s = q ⋅ 2
k
– 1, которое < 3
k
. Предположим,
что
s представлено в виде суммы k-х степеней (не обязательно разных) положи-
тельных целых чисел. Почему в этом случае могут быть только
k-е степени 1
или 2? Используйте выражение
s = (q –1) × 2
k
+ (2
k
– 1) ⋅ 1
k
, чтобы доказать, что
s представляет собой сумму (q – 2 + 2
k
) k-х степеней и не менее. Таким образом,
существуют целые числа, которые можно представить в виде суммы
[3
k
/2
k
] – 2 + 2
k
k-ых степеней и не менее. Что это даёт для k = 2, 3, 4? [Это связа-
но с проблемой Варинга; см. ниже].

Страницы