1. Введение
Как известно, в
последовательности натуральных чисел 1, 2, 3, 4, … любое число, большее
единицы, имеет не менее двух делителей: единицу и самого себя. Всякое
натуральное число p > 1, имеющее
ровно два делителя, называют простым.
Если же делителей больше двух, то число называют составным.
В данной статье обсудим
некоторые неопределенности, возникающие при исследованиях простых чисел.
2. Теорема или гипотеза
В предисловии к [1], выдающийся польский математик
Вацлав Серпинский пишет: «Математика считается, и справедливо, наукой дедуктивной.
Тем не менее не следует умалять роль, которую сыграла в математике индукция, и
притом не так называемая полная индукция, а индукция, основанная на наблюдении
большого числа случаев и ведущая от них к предполагаемым общим теоремам.
Особенно это относится к учению о простых числах, где именно таким путем было
открыто много важных теорем, доказательства которых были найдены позднее. Но
этот путь часто приводил и к ошибочным предположениям…»
В качестве иллюстрации
рассмотрим четыре теоремы П. Ферма, приведенные им в письме к Мерсенну от
1641 г. [1, 2]:
Ни одно из
простых чисел вида a(k) не является делителем ни одного из чисел вида b(n), где
|
Номер теоремы |
a(k) |
b(n) |
|
1 |
12k – 1 |
|
|
2 |
12k + 1 |
|
|
3 |
10k – 1 |
|
|
4 |
10k + 1 |
|
В настоящее время известно,
что
а) теорема 1 является
справедливой;
б) теоремы 2 – 3 неверны
(например, 61 делит 
241 делит 
29 делит 
521 делит 
Продемонстрируем, что вопрос
«Теорема или гипотеза» возникает и при анализе ряда современных исследований.
Рассмотрим, например,
числовые таблицы размера 4´4, в которых числа 1, 2, …,
16 расставлены таким образом, что их сумма в строках, столбцах и главных
диагоналях одинакова. В математике такие таблицы принято называть магическими квадратами 4-го порядка.
Будем говорить, что
магический квадрат порядка 4 обладает структурой,
если из его 16-и различных чисел можно составить 8 пар чисел с суммой равной
1/2 от магической постоянной квадрата. Для получения рисунка структуры магического квадрата достаточно прямо в магическом
квадрате соединить линиями каждую из образующих структуру пару чисел.
В [3 – 5] установлено, что с
точностью до некоторых преобразований
(поворотов, отражений и М-преобразований), магические квадраты 4´4 из чисел от 1 до 16 (классические магические квадраты 4´4) могут иметь всего 6
различных рисунков структур.
Можно ли из простых чисел
построить такие магические квадраты 4´4, которые имеют рисунки
структур, отличные от рисунков структур классических магических квадратов 4´4?
В [5] доказано, что
ни в одном магическом квадрате 4´4, обладающем рисунком структуры и составленном из произвольных 8-и
четных и 8-и нечетных чисел, нельзя найти никаких других рисунков структур
кроме тех, которые имеют магические квадраты из чисел от 1 до 16.
Это утверждение неверно, так
как можно доказать {подробности см. в
[4]}, что
a) в магических квадратах 4´4, обладающих рисунком структуры и составленных из произвольных 8-и
четных и 8-и нечетных чисел, можно найти с точностью до поворотов, отражений и
М-преобразований еще шесть новых рисунков структур, которые не встречаются у
магических квадратов из чисел от 1 до 16;
b) ни в одном магическом квадрате 4´4, обладающем рисунком структуры, нельзя найти с точностью до
поворотов, отражений и М-преобразований никаких других рисунков структур кроме
тех, которые встречаются у магических квадратов из произвольных 8-и четных и
8-и нечетных чисел.
Приведем примеры наименьших магических
квадратов 4´4 из простых чисел, которые
имеют рисунки структур, отличные от рисунков структур классических магических
квадратов 4´4 [6]:
|
83 |
61 |
13 |
71 |
|
101 |
7 |
67 |
53 |
|
1 |
47 |
107 |
73 |
|
43 |
113 |
41 |
31 |
á1ñ
|
461 |
2 713 |
881 |
1 453 |
|
823 |
2 141 |
2 293 |
251 |
|
2 503 |
41 |
1 033 |
1 931 |
|
1 721 |
613 |
1 301 |
1 873 |
á2ñ
|
67 |
2 243 |
1 187 |
1 123 |
|
1 979 |
859 |
331 |
1 451 |
|
727 |
1 319 |
2 111 |
463 |
|
1 847 |
199 |
991 |
1 583 |
á3ñ
3. Теоремы из будущего
Согласно теореме Дирихле (см. например, [7, С.151])
Если f(x) = bx+a и a и b — такие целые числа, что a ¹ 0, b³1 и НОД(a, b) = 1, то существует бесконечно много целых значений m, при которых f(m) — простое число.
В [8] высказано следующее предположение о простых числах в
семействе из s линейных полиномов:
Пусть 
и 
— целые числа; 
семейство 
состоит из таких линейных полиномов 
что не существует целого
числа n > 1, делящего все произведения вида 
где k — произвольное целое число.
Тогда
(a)
существует бесконечно много натуральных значений m, при которых 
— простые числа;
(b) существует
натуральное значение m, при котором — простые числа.
В данном Разделе приведем
некоторые утверждения из [7], при доказательстве которых использовалось
предположение о справедливости указанной гипотезы Диксона.
(S1) Пусть — целые числа;
семейство состоит из таких линейных полиномов 
(i=1, 2, …, s), что
выполнено предположение Диксона.
Тогда существует бесконечно много натуральных
значений m, при которых 
— последовательные простые числа.
Из (S1) выводится, что
а) справедлива
гипотеза Полиньяка: Существует такое k > 0, что количество пар соседних простых чисел 
для которых 
бесконечно (в
частности, бесконечно количество простых чисел-близнецов);
б) для любого целого 
существует 2m последовательных простых
числа, образующих m пар из простых
чисел-близнецов;
в)
существует бесконечно много арифметических прогрессий из n последовательных простых чисел, чья разность d кратна произведению всех простых чисел, не превосходящих n.
(S2) Существует бесконечно много арифметических прогрессий, состоящих из n простых чисел Софи Жермен {из n пар простых чисел (p, 2p+1)}.
(S3) Существует бесконечно много составных чисел Мерсенна 
(S4) Справедлива следующая (знаменитая) гипотеза Артина:
Если a — целое число, которое не является числом 0, –1 или квадратом,
то существует бесконечно много таких простых чисел p, что a — примитивный корень по модулю p.
4. Изменяющиеся постоянные
Обозначим через p(x) количество всех простых чисел, не превосходящих x. В 1850 г. Чебышев
продемонстрировал, каким образом можно определить порядок значений функции p(х).
Он, в частности, доказал [9], что
C1 х /ln х < p(х) < C2 х /ln х,
где значения постоянных C1 и C2 очень близки к 1. При х ³ 30,
например, C1 = 
0,92129… и C2 = (6/5)C1 = 1,10555…
В 1892 г. Сильвестер (Sylvester)
получил более точные оценки для
постоянных C1 и C2: C1 = 0,95695… и C2 = 1, 04423… (при достаточно большом х). B [10] получено, что C1 = 1 + 1/(2 ln х) {при х³ 59} и C2=1+ 3/(2 ln х) {при х> 1}.
Пусть p(a, d) — наименьшее простое число
в арифметической прогрессии a, a+d, a+2d, …,
{НОД(a, d) = 1} и p(d) = max (p(a, d)) при 1 £ a < d .
В [11] доказана теорема (являющаяся одним из серьезных результатов
аналитической теории чисел):
Существуют
такие постоянные 
и L, что p(d) < 
для любого d > 
Значение абсолютной постоянной Линника L неоднократно вычислялось.
Как указано в [7], в 1958 установили, что L £ 5 448; в 1977 — L £ 80,
в 1989 — L £ 13,5; в 1992 — L £ 5,5.
5. Простое или составное
Все существующие современные тесты для проверки
натурального числа N на
простоту разделим условно на
a) пригодные для проверки произвольных чисел
(1) или только чисел специальной формы (2);
b) строго (1) или нестрого (2) обоснованные;
g) позволяющие провести окончательный (1)
или всего лишь предварительный (2) анализ.
Используя указанную
классификацию, для тестов из [7, 12] получим следующие характеристики:
а) APR-тест (используются
результаты из теории алгебраических чисел) и ECPP-тест (используются результаты
из теории эллиптических кривых) — a1,b1,g1;
б) тест Миллера (используется
некоторое обобщение гипотезы Римана) — a1,b2,g2;
в) вероятностные тесты — a1,b1,g2;
г) тест Люка – Лемера (для проверки на простоту
чисел Мерсенна 
— a2,b1,g1.
Парадокс состоит в том, что
для достаточно большого числа N по
результатам компьютерного исследования на простоту (независимо от
характеристик используемых тестов) можно установить только, является или нет
тестируемое число кандидатом в
простые числа.
Например, в [13] указано,
что числа вида 
являются простыми при n = 17, 19,
73, 139 è 907 и
кандидатами в простые числа при n
= 1 907, 2 029, 4 801, 5 153 и 10 867.
Литература
[1] Sierpiński, W. Co wiemy
a czego nie wiemy o liczbach pierwszych. – Warszawa, 1961.
[2] Чебраков Ю.В. Что знали и чего не знали о простых числах в 1960 году? // В книге: Рибенбойм П. Рекорды в исследованиях простых чисел. – СПб.: Изд-во С.-Петерб. ун-та (НИИХ), 2002. – P.10-20.
[3] Andrews, W.S. Magic squares and
cubes. –
Dudeney, H. E. Amusement in
mathematics. –
[4] Чебраков, Ю. В. Магические квадраты. Теория чисел, алгебра, комбинаторный анализ. – СПб: СПб гос. техн. ун-т, 1995.
[5] Ollerenshaw, K. and Bondi, H. Magic squares of order four // Phil. Trans. R. Soc. (Lond.) A 306, 1982, P.443–532.
[6] Чебраков, Ю. В. Как строить из простых чисел числовые таблицы с заданными свойствами? // В книге: Рибенбойм П. Рекорды в исследованиях простых чисел. – СПб.: Изд-во С.-Петерб. ун-та (НИИХ), 2002. – С.191–248.
[7] Рибенбойм, П. Рекорды в исследованиях простых чисел. – СПб.: Изд-во С.-Петерб. ун-та (НИИХ), 2002.
[8] Dickson, L.E. (1904) A new extension of Dirichlet's theorem on prime numbers / Messenger of Math., 33, 1904. P.155–161.
[9] Чебышев, П. Л. Об
определении числа простых чисел, не превосходящих данной
величины. О простых числах. // В книге: Чебышев, П. Л. Полное собрание
сочинений в 3–х томах. Т.1. М., Л.: АН СССР, 1944.
[10] Rosser, J.B. and Schoenfeld, L. Approximate formulas for some functions of prime numbers / Illinois J. Math., 6, 1962. P.64–94.
[11] Линник, Ю.В. О
наименьшем простом в арифметической прогрессии I. Основные
теоремы / Мат. Сборник, 15 (57), 1944. С.139–178.
[12] Wagon, S. Primality testing / Math.
Intelligencer, 8, No. 3, 1986.
P.58–61.
Cohen, H. A Course in Computational Number
Theory. –
Atkin, A.O.L. and Morain, F. Elliptic curves and primality proving / Math. Comp., 61, 1993. P.29–68.
Коутинхо С. Введение в теорию чисел. Алгоритм RSA. – М.: Постмаркет, 2001.
[13] Dubner, H. Generalized repunit primes / Math. Comp., 61, 1993. P.927–930.