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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

5
4. Существует немало эффектных алгебраических разложений на со-
множители, предложенных Е. Лукасом, например, a
10
+ 1 = (a
2
+ 1)((a
4
+
+ a
3
+ 7a
2
+ 5a + 1)
2
– 10a (a
3
+ 2a
2
+ 2a + 1)
2
). Смысл этого выражения за-
ключается в том, что, если 10a является полным квадратом, то вторым со-
множителем будет разность двух квадратов и т. д. Докажите эту формулу и
приведите несколько примеров, в которых a = 10
3
.
5. Обратите внимание на то, что для любого k ≥ 2 можно найти k – 1
чисел вида k! + 1, k! + 3, . . . , k! + k, являющихся составными. Таким обра-
зом, промежутки между последовательными простыми числами могут быть
произвольно большими. Например, когда k = 8, числа 40 322, . . . ,
40 328 все являются составными. Но они не являются наименьшими семью
последовательными составными числами. Найдите
эти числа в диапазоне до
числа 100. Выберите первые 13 последовательных составных чисел, начи-
ная со 114.
6. Пусть n является нечетным составным числом. Покажите, что (2
n
+
+ 1)/3 – число нечетное и составное.
7. Пусть n будет составным числом. Покажите, что (10
n
– 1)/9 – число
составное. Заметим, что полученный результат имеет вид 10
n-1
+10
n-2
+ ... +
+ 10
1
+ 1, т. е. представляет собой целое число! Оно имеет десятичное пред-
ставление, состоящее из n одних единиц, и называется репунит. Реально не
так много простых репунитов известно в случае, если n > 8. Приведенный
здесь результат показывает, что для простых репунитов число n должно
быть также простым; попробуйте n = 3 и 5, чтобы убедиться,
что обратная
теорема не верна.
8. Предположим, что а и с – целые числа, большие единицы. Покажи-
те, что разложение (2
ab
– 1) = (2
a
– 1)(2
c
– 1) невозможно. Вывод: если n
имеет два различных собственных делителя (собственные делители не рав-
ны ±1 и ± n), тогда 2
n
– 1 не может быть произведением двух простых чисел.
[Покажите, что 2
n
– 1 имеет минимум три собственных делителя; сравните
первую формулу из п. 1.1 (3)]. Покажите, что если n = c
k
для c ≥ 2, k ≥ 3, то-
гда 2
n
– 1 не может быть произведением двух простых чисел. Что может это
означать для тех n, у которых 2
n
– 1 представляет собой произведение двух
простых сомножителей?
9. Пусть p будет простым числом, а k – нечётным целым числом ≥1, и
предположим, что p + 1 = 2
t
s, где s – нечетное число. Покажите, что есть
только число 2
t
и нет никакого другого числа более высокой степени 2, ко-
торое делит p
k
+ 1. [ Подсказка: используйте биномиальную теорему ].
2. Наибольший общий делитель и наименьшее общее кратное
2.1. Упражнения
1. Покажите, что если (a, b) = 1 и (a, с) = 1, то (a, bс) = 1.

Страницы