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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

37
6. Покажите, что если p – простое число, тогда x
2
≡ y
2
(mod p) означа-
ет, что x ≡ ±y (mod p). [p | (x – y)(x + y), где р – простое число]. Приведите
пример, показывающий, что это не выполняется, если р – составное число.
7. Особым случаем пункта 6 будет x
2
≡ 1 (mod p), означающий, что
x ≡ ± 1 (mod p). Покажите, что если р – нечётное простое число и k ≥ 1, то-
гда x
2
≡ 1 (mod p
k
), означающее, что x ≡ ± 1 (mod p
k
). [C нашей точки зрения
это значит, что p
k
| (x – 1)(x + 1) и (x – 1, x + 1) = 1 или 2, так как p не может
быть делителем обоих коэффициентов].
8. Покажите, что если p – простое число и k ≥ 1, тогда x
2
≡ x (mod p
k
),
что равноценно сравнениям x ≡ 0 или х ≡ 1 (mod p
k
). [Исключительным слу-
чаем будет, если (х, х – 1) = 1].
9. Пусть n будет простым числом ≥ 0 и пусть х =
41n
⎡⎤
+
⎣⎦
, y =
=
42n
⎡⎤
+
⎣⎦
, z = 43n
⎡⎤
+
⎣⎦
. Используйте первую половину п. 2, чтобы пока-
зать, что из этих трёх квадратных корней только первый, возможно, будет це-
лым числом. Далее покажите, что если k – целое число и x ≤ k ≤ z, тогда k = x.
[Вы можете рассмотреть x ≤ k < y и y ≤
k ≤ z отдельно]. Докажите, что x = y = z.
10. Покажите, что для любого простого числа n
41n
⎡⎤
+
⎣⎦
≤
≤
1nn++
≤ 43n
⎡⎤
+
⎣⎦
. Выведите из п. 9, что x = y = z = [
1nn++
].
11. Пусть r
n
– число (10
n
– 1)/9, чьё десятичное представление содер-
жит n единиц. Покажите, что d | r
n
, если и только если 10
n
≡ 1 (mod 9d). По-
кажите, что если d | r
a
и d | r
b
, тогда d | r
a+b
, и если a > b, тогда d | r
a – b
.
12. Пусть n = a
0
+ 10 a
1
+ 10
2
a
2
+ . . . + 10
k
a
k
, где 0 ≤ a
i
≤ 9 для всякого
i такого, что десятичное представление числа n будет a
k
a
k–1
. . . a
1
a
0
. По-
кажите, что для модуля 3 или модуля 9, n ≡ a
k
+ a
k
–
1
+ . . . + a
1
+ a
0
. Докажи-
те хорошо известный тест делимости на 3 или 9: число делится на 3 (соот-
ветственно, 9), если и только если сумма их десятичных цифр делится на 3
(соответственно, 9).
13. Аналогично покажите, что число делится на 11, только и если
только альтернативная сумма a
k
– a
k–1
+ a
k–2
– . . . ±a
0
делится на 11.
14. Предположим, что a, b, c, d, x, y – целые числа, удовлетворяющие
выражениям: (ad – bc, m) = 1 и ax + by ≡ 0 (mod m), cx + dy ≡ 0 (mod m). По-
кажите, что х ≡ 0 и y ≡ 0 (mod m). [Как в случае обыкновенных линейных
уравнений, сократите у умножением первого сравнения на d, а второго на b
с последующим вычитанием].
15. Предположим, что р – простое число, а а > 1, m ≥ 1 являются це-
лыми числами такими, что a
2m
≡ – 1(mod p). На основании этого покажите,
что наибольший общий делитель a
2m
+ 1 и a
2n
+ 1 будет 1, если а – чётное, и
2, если a – нечётное. [Подсказка. Покажите, что если р – делитель обоих чи-
сел, тогда p | 2].

Страницы