Ю. В. Матиясевич |
Простые числа разбросаны в натуральном ряду очень прихотливым образом, и не удивительно, что издревле математики стремились найти «формулу для простых чисел». Такими формулами можно называть формулы, обладающие разными свойствами, и здесь очень важно понять, что нам требуется на самом деле.
Самая простая формула для простых чисел выглядит,
p = pn , | (1) |
где pn обозначает n-е простое число. Чем же эта формула не устраивает нас? Дело в том, что правая часть этого равенства вычисляется слишком сложным образом попробуйте, например, самостоятельно найти p1975! Мы же хотим получить аналогичную формулу с возможно более простым способом вычисления правой части (однако, как мы увидим, простота вычислений понятие совсем не очевидное). Это, так сказать, программа-максимум.
Ради простоты формулы можно отказаться от требования явной зависимости от
Формулы, кажущиеся очень простыми, на деле могут оказаться не лучше
В 1947 году В. X. Миллс опубликовал следующий результат:
Существует вещественное число λ такое, что при любом
[ λ3ⁿ ] | (2) |
является простым 1.
Впоследствии появился ещё ряд формул такого же типа. Однако все это были результаты, формулировка которых выглядит заманчивой и многообещающей, но доказательство разочаровывает. Тому, кто хочет понять, почему это так, мы предлагаем разобраться в доказательстве следующей теоремы Е. М. Райта:
Существует вещественное число μ такое, что всякое число вида
|
(3) |
является простым.
Ключевым пунктом в доказательстве теоремы Райта является так называемый постулат Бертрана. Согласно этому постулату при
Чтобы найти нужное число μ выберем сначала последовательность простых чисел q1,
|
(4) |
(В качестве q1 можно взять любое простое число, возможность же неограниченного продолжения последовательности
Обозначим для краткости число
22 |
...2 | α |
где берётся n возведений в степень, через
через
Попробуем выбрать число μ так, чтобы при
[exp2nμ] = qn . | (5) |
Согласно определению целой части числа
Прологарифмировав его n раз по
log 2nqn ≤ μ < log 2n(qn + 1). | (6) |
Проверьте сами, что из (4) следует
Таким образом, последовательность
строго возрастает и ограничена сверху; следовательно, она имеет предел.
log 2nqn < μ < log 2n(qn + 1), | (7) |
и, следовательно, равенство (5) справедливо. Теорема Райта доказана.
Основным недостатком формул (2) и (3) является то, что они (точнее, их доказательства) не дают никакого способа находить новые простые числа, ибо чтобы вычислить
Недостатки формул (2) и (3) порождены тем, что в них входят вещественные числа
Формулы Миллса, Райта и другие подобные формулы остались изолированными фактами, не приведшими к новым результатам. Однако в других случаях возможность представить некоторые простые числа в том или ином специальном виде имеет неожиданные и глубокие следствия.
Рассмотрим сейчас две формулы, имеющие совсем простой вид:
p = 2n 1, | (8) |
p = 2n + 1. | (9) |
Очевидно, что формула (8) не всегда даёт простые числа; например, если n составное число,
Простые числа, получающиеся по формуле (8), называются числами Мерсенна в честь Марена Мерсенна, который ещё в 1664 году указал все простые
Интерес к числам Мерсенна вызван их связью с так называемыми совершенными числами числами, равными сумме всех своих делителей, отличных, конечно, от самого числа. Ещё Евклид доказал (докажите и вы), что если простое
простые числа, и соответственно
6 = | (3 · 4)/2 = 1 + 2 + 3, |
28 = | (7 · 8)/2 = 1 + 2 + 4 + 7 + 14 |
совершенные числа. Спустя несколько столетий Леонард Эйлер доказал (попробуйте и здесь свои силы), что все чётные совершенные числа имеют вид, указанный Евклидом. Таким образом, вопрос, конечно или бесконечно множество чётных совершенных чисел, свёлся к вопросу, конечно или бесконечно множество простых чисел Мерсенна, то есть к вопросу, реализует ли
Формула (9) также не всегда даёт простые числа, например, если n имеет простой нечётный
Простые числа Ферма обнаруживают неожиданную связь с геометрией. Выдающийся немецкий математик Карл Фридрих Гаусс доказал, что правильный
Формулы (8) и (9) содержат возведение в степень. А нельзя ли для задания бесконечно многих простых чисел обойтись лишь сложением, вычитанием и умножением? Поищем ответ на этот вопрос.
Начнём с рассмотрения многочленов от одной переменной с натуральными коэффициентами; посмотрим, какие многочлены будут своими значениями иметь простые числа и в каком количестве.
Возьмём вначале многочлены первой степени (то есть линейные многочлены). Очевидно, что тривиальный
Французский математик Лежандр (живший в XVIII веке) высказал гипотезу, что
Перейдём теперь к квадратным многочленам. Среди них есть «рекордсмены», например, многочлен
Доказано, что никакой многочлен (отличный, разумеется, от константы) не может иметь в качестве значений только простые числа, но до сих пор не известно, существует ли многочлен (кроме линейного), среди значений которого встречается бесконечно много простых чисел.
Интерес к представлению простых чисел в виде значений квадратных многочленов недавно возродился в связи с неожиданным наблюдением С. М. Улама 5. Начав на спирали из всех натуральных чисел (рис. 1) отмечать простые числа, Улам с удивлением обнаружил, что простые числа выстраиваются по диагоналям, образуя довольно длинные цепочки. (Докажите, что числа, расположенные вдоль
197 | 196 | 195 | 194 | 193 | 192 | 191 | 190 | 189 | 188 | 187 | 186 | 185 | 184 | 183 |
198 | 145 | 144 | 143 | 142 | 141 | 140 | 139 | 138 | 137 | 136 | 135 | 134 | 133 | 182 |
199 | 146 | 101 | 100 | 99 | 98 | 97 | 96 | 95 | 94 | 93 | 92 | 91 | 132 | 181 |
200 | 147 | 102 | 65 | 64 | 63 | 62 | 61 | 60 | 59 | 58 | 57 | 90 | 131 | 180 |
201 | 148 | 103 | 66 | 37 | 36 | 35 | 34 | 33 | 32 | 31 | 56 | 89 | 130 | 179 |
202 | 149 | 104 | 67 | 38 | 17 | 16 | 15 | 14 | 13 | 30 | 55 | 88 | 129 | 178 |
203 | 150 | 105 | 68 | 39 | 18 | 5 | 4 | 3 | 12 | 29 | 54 | 87 | 128 | 177 |
204 | 151 | 106 | 69 | 40 | 19 | 6 | 1 | 2 | 11 | 28 | 53 | 86 | 127 | 176 |
205 | 152 | 107 | 70 | 41 | 20 | 7 | 8 | 9 | 10 | 27 | 52 | 85 | 126 | 175 |
206 | 153 | 108 | 71 | 42 | 21 | 22 | 23 | 24 | 25 | 26 | 51 | 84 | 125 | 174 |
207 | 154 | 109 | 72 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 83 | 124 | 173 |
208 | 155 | 110 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 123 | 172 |
209 | 156 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 171 |
210 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 |
211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |
Ещё более удивительным оказалось то, что закономерность эта наблюдалась и тогда, когда спираль была продолжена (с помощью компьютера) до больших чисел на рис. 2 светлыми точками отмечены простые числа на спирали из первых 10 000 чисел. Узор, изображённый на рис. 2, получил название «скатерть Улама».
Чтобы отмеченная закономерность проявилась, не обязательно начинать спираль с единицы. Например, значения многочлена
57 | 56 | 55 | 54 | 53 |
58 | 45 | 44 | 43 | 52 |
59 | 46 | 41 | 42 | 51 |
60 | 47 | 48 | 49 | 50 |
61 | 62 | 63 | 64 | 65 |
Возможно, что читатели «Кванта», проявив изобретательность и должное терпение, смогут найти новые красивые «геометрические» закономерности расположения простых чисел среди множества всех чисел.
Феномен со стремлением простых чисел располагаться в цепочки вдоль диагоналей был обнаружен сравнительно недавно и ещё не получил
О представлении простых чисел с помощью многочленов от многих переменных мы скажем в конце статьи.
Экспоненциальные многочлены отличаются от обычных тем, что в них показателями степени могут быть не только конкретные натуральные числа, но и линейные многочлены от переменных с натуральными коэффициентами, то есть многочлены вида
где a1, a2, ..., ak , b целые неотрицательные числа.
Простейшими примерами экспоненциальных многочленов от
В дальнейшем мы всегда будем предполагать, что все встречающиеся у нас переменные принимают целые положительные значения.
В 1952 году американский математик Джулия Робинсон 6 опубликовала следующий замечательный результат:
Существует экспоненциальный многочлен
В результате получается такая «формула для простых чисел»:
p = R(x0, ..., xk ). | (10) |
Эта формула замечательна вот чем.
Доказательство Джулии Робинсон совершенно элементарно. Ниже излагаются его основные идеи; доведение же доказательства до формальной строгости мы оставляем читателям: все промежуточные результаты сформулированы в виде пяти лемм,
Чтобы доказать теорему Джулии Робинсон, мы, очевидно, должны указать экспоненциальный
p простое число. | (11) |
Это пример условия на переменную p.
Приведём ещё несколько примеров условий на набор переменных
λ1, ..., λn, x0, ..., xk . | (11′) |
Если мы потребуем, чтобы набор чисел (11) удовлетворял системе уравнений вида
Fi(λ1, ..., λn, x0, ..., xk ) = 0 (i = 1, ..., s), | (11″) |
или допустим словесное описание типа:
Мы не станем точно определять, условия какого вида являются для нас допустимыми. Приведённое описание примеров условий достаточно для оправдания того способа действий, которым мы в дальнейшем будем пользоваться.
В последующем изложении мы будем различать переменные, называя некоторые из них параметрами, так что деление переменных на параметры и неизвестные у нас является чисто условным.
Если все левые части системы уравнений (11″) являются экспоненциальными многочленами от
Уравнение (10) является примером экспоненциально диофантова уравнения относительно переменных p,
Мы будем говорить, что две системы условий, имеющие одни и те же параметры, эквивалентны друг другу относительно этих параметров, если множество тех значений параметров, при которых имеет решение одна из этих систем, совпадает со множеством тех значений параметров, при котором имеет решение и другая система. (Обратите внимание, что в этом определении ничего не говорится о связи значений неизвестных для наших целей это неважно, эквивалентные в нашем понимании системы могут вообще не иметь общих неизвестных.)
Примером эквивалентных условий относительно
и равенство
Ясно, что каждое из этих условий имеет решение тогда и только тогда, когда
В этой терминологии наша цель формулируется так: найти экспоненциальный многочлен
Однако требование, чтобы параметр p стоял только в левой части
Пусть удалось найти экспоненциальный многочлен
Q(p, x1, ..., xk ) = 0 | (12) |
эквивалентно условию (11).
Положим
R(x0, ..., xk ) = x0·(1 Q 2(x0, ..., xk )). | (13) |
Лемма 1. Если экспоненциальные многочлены R
Нам достаточно даже найти не уравнение, а хотя бы систему экспоненциально диофантовых уравнений
|
(14) |
эквивалентную условию (11)
Лемма 2. Если
l | ||
Q( p, x1, ... , xk ) = | ∑ | Qi2( p, x1, ... , xk ), |
i=1 |
то система (14) эквивалентна уравнению (12).
Именно поиском системы экспоненциально диофантовых уравнений, эквивалентной
«Странный вопрос, удивится читатель. Каждый знает, что простое число это число, большее единицы, которое делится только на единицу и на себя». Конечно, это так, но с таким определением работать нелегко ведь оно предполагает, что проверка простоты числа состоит в переборе бесконечного числа потенциальных делителей всех натуральных чисел,
В этом определении нет ограничения
Сделанное замечание позволяет нам написать первую систему условий, эквивалентную
|
(15) | ||||||
(16) | |||||||
(17) |
Первое из этих условий имеет искомый вид экспоненциально диофантова (более того, диофантова) уравнения, а третье легко приводится к такому же виду за счёт введения двух новых неизвестных:
Лемма 3. Условие (17) эквивалентно относительно параметров p, s условию 9
x1· s x2· p = 1. | (18) |
Так как уравнение (18) экспоненциально диофантово, то нам осталось лишь найти систему экспоненциально диофантовых уравнений, эквивалентную относительно параметров r и s условию (16).
В условие (16) входит r!; этот-то факториал и «мешает» нам. Вспомним, что факториал фигурирует в выражении для биномиальных коэффициентов 10:
|
t(t 1) ... (t r + 1) r! |
, |
то есть
r! = | t(t 1) ... (t r + 1) (tr ) |
. |
Многочлен, стоящий в числителе, имеет довольно сложную структуру. Попытаемся заменить его более простым а именно,
|
(19) |
Легко видеть, что
|
(20) |
однако эта запись факториала нам ничего не даст, поскольку t, будучи параметром в искомой системе уравнений, сможет принимать любые, сколь угодно большие, но конечные значения. Но мы и не будем переходить к пределу, а воспользуемся целочисленностью r! из (19) и (20) следует, что при достаточно
|
(21) |
Лемма 4. Формула (21) верна как только
Лемма 4 позволяет преобразовать условие (16) в эквивалентную ему относительно параметров r и s систему (проверьте эквивалентность!)
|
|
Здесь условия (22), (24) и (25) имеют требуемый вид, и нам остаётся лишь найти систему экспоненциально диофантовых уравнений, эквивалентных условию (23) относительно параметров r, t
Итак, нам осталось «избавиться» от биномиального коэффициента.
Только что мы использовали выражение биномиальных коэффициентов через факториал; но биномиальные коэффициенты имеют много и других определений. Воспользуемся теперь тем, что
|
(26) |
Эта формула является определением биномиальных коэффициентов, если рассматривать её как тождество относительно u. Но нам нужно, чтобы u было неизвестной, принимающей в каждом конкретном решении искомой системы лишь одно значение.
Заметим, что
|
(27) |
и, таким образом, если
u > 2t, | (28) |
то (t0), (t1), ..., (tt) это цифры в записи числа
Лемма 5. Условие (23) эквивалентно относительно параметров r, t, c системе условий
|
(29) (30) (31) (32) (33) |
Здесь все условия уже имеют необходимый нам вид.
Итак, мы показали, что условие (11) эквивалентно относительно
Формула (10) не содержит явно номера задаваемого ею простого числа. Описанный выше способ построения экспоненциального
Существует экспоненциальный многочлен
В 1970 году автору этой статьи удалось, используя другие результаты Джулии Робинсон, построить такое диофантово уравнение:
M(a, b, c, z1, ..., zm) = 0, | (34) |
которое разрешимо тогда и только тогда, когда параметры
1. | Докажите, что в арифметических прогрессиях |
2. | Каково множество тех многочленов, значения которых лежат вдоль диагонали, если спираль начата с 1? начата с некоторого числа u? начата с некоторого числа u, и по спирали стоят члены арифметической прогрессии u, u + v, |
3. | Теорема Вильсона утверждает, что если p простое число, то |
4. | Постройте экспоненциальный многочлен |
5. | Постройте экспоненциальный многочлен если q простое число, то существуют числа если q простое число и если q не является простым числом, то всегда Этот экспоненциальный многочлен даёт «формулу для следующего простого числа». |
1. | Здесь и далее [α] обозначает целую часть | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
2. | Прочитать об этом доказательстве можно в статье М. И. Башмакова, «Квант», 1971, № 5, или в заметке С. Б. Стечкина «Простое доказательство теоремы Чебышёва о простых числах» (УМН, 1968, № 5, | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
3. | Об истории и современном состоянии исследований по совершенным числам и простым числам Мерсенна вы можете прочитать в статье И. Я. Депмана, «Квант», 1971, № 8, или в обзорной статье Вальтера Боро «Дружественные числа» из книги «Живые числа» (М., «Мир», 1985, DjVu, 1875 Кб). | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4. | Подробнее об этом открытии тогда ещё совсем молодого Гаусса рассказано в статье С. Г. Гиндикина, «Квант», 1972, № 1, или в книге «Рассказы о физиках и математиках» (М., МЦНМО, 2001, PDF, 7275 Кб) того же автора, в главе, посвящённой Гауссу. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
5. | Как было сделано это наблюдение, красочно рассказывает М. Гарднер в «Математических досугах» (М., «Мир», 1972). Вот этот кусочек В зависимости от расположения целых чисел простые числа могут образовывать тот или иной узор. Однажды математику Станиславу М. Уламу пришлось присутствовать на одном очень длинном и очень скучном, по его словам, докладе. Чтобы Вблизи центра выстраивания простых чисел вдоль прямых ещё можно было ожидать, поскольку плотность простых чисел вначале велика и все они, кроме В вычислительном отделе Лос-Аламосской лаборатории, где работал Улам, имелась магнитная лента, на которой было записано
Прежде всего бросаются в глаза скопления простых чисел на диагоналях, но вполне ощутима и другая тенденция простых чисел выстраиваться вдоль вертикальных и горизонтальных линий, на которых все клетки, свободные от простых чисел, заняты нечётными числами. Простые числа, попадающие на прямые, продолженные за отрезок, который содержит последовательные числа, лежащие на Начав спираль не с 1, а с какого-нибудь другого числа, мы получим другие квадратичные выражения для простых чисел, выстраивающихся вдоль прямых. Рассмотрим спираль, начинающуюся с Самый знаменитый квадратичный трёхчлен Эйлера, производящий простые числа,
Спираль Улама подняла много новых вопросов, относящихся к закономерностям и случайностям в распределении простых чисел. Существуют ли прямые, на которых лежит бесконечно много простых чисел? Какова максимальная плотность распределения простых чисел вдоль прямых? Существенно ли различаются плотности распределения простых чисел в квадрантах «скатерти» Улама, если считать, что она продолжается неограниченно? Спираль Улама забава, но её следует принимать всерьёз. E.G.A. назад к тексту | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
6. | Точнее, Робинсон получила чуть более слабый результат, а эту изящную форму придал результату Робинсон впоследствии X. Патнам. назад к тексту | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
7. | Полиномиальная формула это формула, задаваемая многочленом. назад к тексту | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
8. | Н.О.Д.(a, b) это наибольший общий делитель чисел a | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
9. | Сравните эту лемму с леммой 2 из «Кванта» № 6 за 1972 год, с. 33. назад к тексту | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
10. | О свойствах биномиальных коэффициентов «Квант» рассказывал неоднократно; см., например, № 6 за 1970 год, |