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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

38
16. Покажите, что для любых целых чисел h и k,
22
0,1, 4(mod8), 0(mod 4),
1, 2, 5(mod 8), 1, 3(mo d 4),
0, 4, 5(mod 8), 2(mod 4) .
если h
hk если h
если h
≡
⎧
⎪
+≡ ≡
⎨
⎪
≡
⎩
Докажите, что не существует решений уравнений
(x + 1)
2
+ a
2
= (x + 2)
2
+ b
2
= (x + 3)
2
+ d
2
,
для целых чисел x, a, b, c, d.
17. Для целого числа n могут ли все числа n + 1, n + 3, n + 7, n + 9, n +
+ 13, n + 15 быть простыми? [Рассмотрите модуль 5].
18. Предположим, что s – простое число и s | (n
p-1
– 1), но s не делит
(n
q
– 1). Покажите, что s не делит (N – 1), где
(1)(1)
(1)(1)
pq
pq
nn
N
nn
−
−
=
−
−
.
Докажите, что 2
16
– 1 является делителем числа
85
17 5
21
1
(2 1)(2 1)
−
−
−−
.
(Заметим, что 2
16
– 1 не является простым числом!).
19. Покажите, что для n чётного, 1 + 2 + 3 + . . . + n ≡ 0 (mod n). Докажи-
те, что когда n – чётное, то невозможно найти перестановку a
0
, a
1
, . . . , a
n–1
последовательности {0, 1, . . . , n – 1] такую, что числа a
1
– a
0
, a
2
– a
1
, . . . ,
a
n–1
– a
n-2
будут все различные (и, конечно, ненулевыми) по mod n. Для чётно-
го n сумеете ли Вы найти такую перестановку? (Такая перестановка иногда
называется прямая терраса).
20. Покажите, что если х ≡ ±1 (mod 3), тогда х
3
≡ ±1 (mod 9). Исполь-
зуйте этот результат, чтобы показать, что невозможно найти целые числа x,
y, z, из которых ни одно не делится на 3, и таких, что x
3
+ y
3
= z
3
. Это «пер-
вый» или «простой» случай последней теоремы Ферма для показателя 3. Её
значительно труднее доказать, чем то, что уравнение не имеет решений для
всех ненулевых целых чисел.
21. Покажите, что если n ≥ 5, тогда 2
n!
≡ 76 (mod 100).
9.2. Проект. Доводя до конца вышеизложенный метод и создавая, та-
ким образом, ряд покрывающих сравнений по всем модулям, которые яв-
ляются делителями 120. Заметим, что наименьшим модулем будет 3. Суще-
ствуют ряды покрывающих сравнений с наименьшим модулем 4; вышепри-
ведённый метод даёт один с N = 720, но также существует ещё один
с N = 360.
9.3. Упражнение. Докажите, что не существует ряда, который осно-
вывается, как показано выше, на делителях числа вида 3
a
5
b
. [Подсказка.
Найдите ∑∑ 3
–r
4
–s
, где r и s принимают значения от 0 до ∞. Потом вычтите
1, чтобы отказаться от r = s = 0; ответом будет < 1].

Страницы