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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

8
3. Покажите разложением на простые сомножители, что [[a, b], c] =
= [[
b, c], a] = [[с, a], b]. Общее значение этих выражений записывается как
[
a, b, c] и называется НОК a, b и c. В общем случае [a
1
, a
2
, . . . , a
n
].
4. Пусть
q
1
< q
2
< . . . < q
8
– восемь нечетных простых чисел и пусть r
будет НОК всех чисел
q
j
,…, q
i
для 1 ≤ i < j ≤ 8. Пусть А = {5, 7, 8, 9}. Пока-
жите, что от деления любого нечетного простого числа на элемент из А
можно получить максимум семь различных остатков. (Например,
q/7 может
иметь остатки 0, 1, . . . , 6, а
q/8 может иметь только остатки 1, 3, 5, 7, так
как
q – нечетное число). Из этого следует, что для каждого m ∈ A, по край-
ней мере, два из
q
i
должны иметь одинаковые остатки, когда делятся на m,
и, следовательно, их разность делится на
m. (Это применение известного
«принципа голубиного гнезда», здесь голубями будут
q
i
, а голубиными
гнездами – остатки). Почему это следует из того, что
r делится на 5, 7, 8 и 9
и, следовательно, на 5 · 7 · 8 · 9 = 2520? Проверьте, что восемь простых чи-
сел 11, 17, 23, 29, 41, 53, 59 дают
r = 5040.
5. Покажите, что max(
i, j, k) = i + j + k – min(j, k) – min(k, i) –
– min (
i, j) + min(i, j, k) для любых чисел i, j и k. [Заметим, что благодаря
симметрии достаточно проверить формулу при
i ≤ j ≤ k]. Докажите, что для
натуральных чисел
a, b и с, верна формула
[]
(,,)
,, .
(,)(, )(,)
abcabc
abc
bc ca ab
=
6. Предположим, что (
a, b) = 1 и d | ab. Докажите, что существуют
единственные числа
d
′
и d
′′
, для которых d = d
′
d
′′
, d
′
|a, d
′′
|b. Автоматиче-
ски это выполняется, если (
d
′
, d
′′
) = 1. Докажите обратное утверждение: ес-
ли
d
′
| a и d
′′
| b, тогда d
′
d
′′
| ab, так что произведение делителей ab одно-
значно определяет пару делителей
a и b.
3. Алгоритм Евклида
3.1. Теорема. Для любого целого числа k верна формула:
(
a, b) = (a + kb, b).
Доказательство. Простейшим путем для доказательства этого будет
показ того, что ряд из общих делителей
a + kb и b совпадает с рядом общих
делителей
a и b, т. е. d | a и d | b ⇔ d | (a + kb) и d | b. Этот факт более или
менее быстро следует из определения делителя. Следствием этого является
то, что
наибольший общий делитель для a и b равен НОД для a + kb и b.
3.2. Упражнения
1. Используйте п. 3.1, чтобы показать, что (6n + 1, 6n – 3) = 1 для лю-
бого целого числа
n. [Возьмите k = –1]. Покажите также, что (5n + 3,
3
n + 2) = 1, конечно, сначала доказав, что (5n + 3, 3n + 2) = (2n + 1, 3n + 2).

Страницы