Главная > Математика > Введение в теорию чисел. Алгоритм RSA
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 1.6. Проблемы теории чисел

Нельзя завершить введение в теорию чисел, не попытавшись хотя бы объяснить, почему она настолько пленительна, что Гаусс назвал ее «королевой математики». Лучше всего создать представление о ее привлекательности, сформулировав несколько проблем; при простой формулировке их решение зачастую требует изобретательности и виртуозного владения техникой.

Перечислим некоторые вопросы теории. Прочитав их, Вы можете попробовать расставить их по уровням сложности.

Возможно, приводимое ниже описание современного положения дел с их решением удивит Вас.

1) Верно ли, что для любого простого числа разность делится на ?

2) Существует ли такое простое число что делится на

3) Верно ли, что всякое четное число, большее 2, представляется в виде суммы двух простых чисел?

4) Существуют ли два последовательных натуральных числа, отличных от 8 и 9, каждое из которых является степенью простого числа?

5) Всякое ли нечетное простое число можно представить в виде суммы двух квадратов натуральных чисел?

6) Бесконечно ли множество пар простых чисел

7) Бесконечно ли множество таких простых чисел что число также простое?

Вопросы (1) и (2) очень похожи друг на друга. Более того, сравнивая их, можно даже прийти к заключению, что второй вопрос легче первого. Ведь для его решения достаточно просто привести пример простого числа, удовлетворяющего некоторому свойству, тогда как в первом вопросе что-то похожее утверждается про все простые числа. Однако положительный ответ на вопрос (1) был получен Ферма в семнадцатом веке, тогда как вопрос (2) до сих пор остается открытым.

Третий вопрос представляет собой знаменитую гипотезу Гольдбаха, и хотя он был поставлен более двухсот лет назад, ответ на него до сих пор не найден. Четвертый вопрос известен под именем гипотезы Каталана (Catalan); он также остается открытым. Однако известно, что если разность

между некоторым кубом и некоторым квадратом равна ±1, то этот куб равен 8, а квадрат равен 9. Доказательство принадлежит Эйлеру, и оно не очень сложное. Подробнее о гипотезе Каталана см. [42].

Ответ на вопрос (5) отрицателен. Если остаток от деления простого числа на 4 равен 3, то не существует таких целых чисел х и у, что Этот результат принадлежит Ферма; его доказательству посвящено упражнение 13 главы 5. Однако Ферма показал заодно, что если остаток от деления простого числа на 4 равен 1, то ответ на вопрос утвердительный. Подробности см. в упражнении 14 главы 6. История проблемы обсуждается в [49] ([Д.13]).

Вопрос (6) — это знаменитая проблема о простых числах-близнецах, и ответ на него неизвестен. Про бесконечность множества простых чисел знал, разумеется, еще Эвклид; его доказательство содержится в § 4.5. Известно также, что для любой пары натуральных чисел о и с наибольшим общим делителем равным 1, множество простых чисел вида о где k — натуральное число, бесконечно. Это утверждение было доказано Дирихле в 1837 году. Доказательству весьма частного случая этого утверждения посвящены упражнения с по главы 4. Еще один близкий вопрос — бесконечно ли множество простых чисел для которых тоже простые; ответ на него также неизвестен. Однако простое число для которого тоже простые, единственно; см. упражнение 9 главы 4.

Последний вопрос тоже представляет собой открытую проблему. Числа вида называются числами Мерсенна по причинам, которые объясняются в § 4.2. Если число в показателе степени составное, то составным является и число Однако число Мерсенна, отвечающее простому показателю, может быть как простым, так и составным. В § 10.4 мы изучим эффективный тест на простоту для чисел Мерсенна. Наибольшие из известных простых чисел имеют такой вид, и

для доказательства их простоты использовался именно этот тест.

<< Предыдущий параграф Следующий параграф >>
Оглавление