Формулы для простых чисел

5

Что требуется?

Простые числа разбросаны в натуральном ряду очень прихотливым образом, и не удивительно, что изделия математики стремились найти «формулу для простых чисел». Таким образом можно назвать формулы, обладающие различными свойствами, и здесь очень важно понять, что нам требуется на самом деле.

Самая простая формула для простых чисел выглядит, по-видимому, так:

$$p = p_n,$$

(1)

где $p_n$ обозначает $n$-е простое число. Чем же эта формула не устанавливает нас? Дело в том, что права часть этого равенства вычисляется с помощью образом — попробyte, например, самостояльно найти $p_{1975}$! Мы же хотим получить аналогичную формулу с возможно более простым способом вычисления правой части (однако, как мы видим, простота вычисления — понятие совсем не оченьное). Это так сказаить, программа-маскимут.

Ради простоты формулы можно отказывать от требования явной зависимости от номера $n$ и искать формулы, дающие простые числа, быть может, не по порядку. Далее, можно отказывать от желания задать одной формулой сразу все простые числа и требовать только того, чтобы формула давала бесконечно много простых чисел. Можно, наконец, допустить, чтобы эта формула давала наряду с бесконечно много простыми числами и нековотые составные числа. Это — программа-минимум.

Формулы, каждщесяя очень простыми, надел могут оказаться не лучшие формулы (1). Именно к таким примерам мы сейчас и переходим.

Teorema E. M. Райта

В 1947 году В. X. Милл с опубликовал следующий результат:

Существует вещественное число $\lambda$ макое, что при любом $n=1, 2, \dots$ число

$$[\lambda^{3^n}]$$

(2)

является простым *).

В последствии появился еще ряд формул такого же типа. Однако все это были результаты, формулировка которых выглядит заманчивой и многообещающей, но доказательство разочаровывает. Тому, кто хочет понять, почему это так, мы предлагаем разобрать в доказательстве следующей теоремы E. M. Райта:

Существует вещественное число $\mu$ макое, что всякое число вида

$$[2^2 \cdot 2^{\mu}]$$

(3)

является простым.

Ключевым пунктом в доказательстве теоремы Райта является так называемый постулат Бертрана. Согласно этому постулату при $x \geq 4$ между $x$ и $2x-2$ всегда есть

*) Здесь и ниже [$\alpha$] обозначает целую часть числа $\alpha$, то есть наиболее целое число, не превышает $\alpha$.

6

простое число. Эту гипотезу впервые высказал французский математик Бертран: докаазать ее он не смог, а потому использовал в своих рассужdenях в качестве недоказуемого построата. Докаазательство гипотезы Бертрана было найдено впоследствии выдающимся русским математиком П. Л. Чебышевым *).

Чтобы найти нужное число μ, выберем сначала последовательность простых чисел $q_1, q_2, \dots$, такую, что при любом $n=1, 2, \dots$
$$2^q < q_{n+1} < 2^{q+1} - 1. \quad (4)$$
(B качестве $q_1$ можно взять любое простое число, возможно же неограниченного продолжения последовательности $\{q_n\}$ с соблюдением неравенства (4) гарантирует построат Бертрана.)

Обозначим для краткости число
$$2^2,$$
где берется $n$ возведений в степень, через $\exp^n \alpha$, а обратную функцию,
$$\log_2 \log_2 \dots \log_2 \beta - \text{через } \log_2^n \beta.$$

Попробуем выбрать число μ так, чтобы при $n=1, 2, \dots$
$$[\exp^n \mu] = q_n. \quad (5)$$
Согласно определению целой части числа равенство (5) эквивалентно неравенству
$$q_n \leqslant \exp^n \mu < q_n + 1.$$

Пропагандировав его $n$ раз по основанию 2, получим еще одно двойное неравенство, эквивалентное (5):
$$\log_2^n q_n \leqslant \mu < \log_2^n (q_n + 1). \quad (6)$$

Проверьте сами, что из (4) следует
$$\log_2^1 q_1 < \log_2^2 q_2 < \dots < \log_2^n q_n < \log_2^{n+1} q_{n+1} < \dots < \log_2^{n+1} (q_{n+1} + 1) < \log_2^n (q_n + 1) < \dots < \log_2^2 (q_2 + 1) < \log_2^1 (q_1 + 1).$$

Таким образом, последовательность
$$\log_2^1 q_1, \log_2^2 q_2, \dots, \log_2^n q_n, \dots$$
строго возрастает и ограничена сферу; следовательно, она имеет предел. Его-то мы и возьмем в качестве числа μ; докажите, что так выбранное μ удовлетворяет даже более сильному, чем (6), неравенству
$$\log_2^n q_n < \mu < \log_2^n (q_n + 1), \quad (7)$$
и, следовательно, равенство (5) справедливо. Теорема Райта доказана.

Основным недостатком формул (2) и (3) является то, что они (точнее, их доказательства) не дают никакого

*) Прочитать об этом доказательстве можно в статье М. И. Башмакова, «Квант», 1971, № 5.

способа нахождения простые числа, либо чтобы вычислить какое-лобо простое число по формулам (2) или (3), нужное число λ и μ знать с достаточной точностью. Таким образом, формулы (2) и (3) в некоторых смысле являются всего лишь замакированными (иухудшенными) вариантами формулы (1). Кроме того, вид формул (2) и (3) на самом деле почти ничего не говорит именно о множестве простых чисел. Из доказательства теоремы Райта видно, что формулы, аналогичные (2), (3), можно указать для любого «достаточного густаго» множества.

Недостатки формул (2) и (3) порождают тем, что в них входят вещественные числа λ и μ, задаваемые некоторым косвенным образом. В дальнейшем мы будем рассматривать лишь формулы, в которых входят только целочисленные коэффициенты. Такие формулы обладают важным преимуществом: они могут быть (в принципие) выписаны явно:

Простые числа Мерсенна и Ферма
Формулы Милласа, Райта и другие подобные формулы остались изолированными фактами, не приведшими к новым результатам. Однако в других случаях возможность представить некоторых простых числа в том или ином специальном виде имеет неожиданные и глубокие следствия.

Рассмотрим сейчас две формулы, имеющие совместим простой вид:
$$p = 2^n - 1, \quad (8)$$
$$p = 2^n + 1. \quad (9)$$

Очевидно, что формула (8) не всегда дает простые числа; например, если $n$ — составное число, $n = kl, k > 1, l > 1$, то $p$ делится на $2^k - 1$ и на $2^l - 1$. Но и при простом $n$ получающейся по формуле (8) число может оказаться составным:
$$2^{11} - 1 = 2047 = 23 \cdot 89.$$

Простые числа, получающие по формуле (8), называются числами Мерсенна в числе Марина Мер-

7

сенна, который еще в 1664 году указал все простые значения $n$, не превосходящие 257, для которых, по его мнению, формула (8) дает простые числа. Однако Мерсенн не дал доказательства; впоследствии выяснили, что его предсказание было частично ошибным.

Интерес к числам Мерсенна вызван их связью с так называемыми совершенными числами — числами, равными сумме всех своих делительей, отличных, конечно, от самого числа. Еще Евклид доказал (доказатель и вы), что если простое число $p$ имеет вид, указывающий в формуле (8), то число $p \cdot (p+1)/2$ является совершенным. Например,

$$3 = 2^2 - 1, \quad 7 = 2^3 - 1$$

— простые числа, и соответственно

$$6 = (3 \cdot 4)/2 = 1 + 2 + 3, \quad 28 = (7 \cdot 8)/2 = 1 + 2 + 4 + 7 + 14$$

— совершенные числа. Спустя несколько столетий Леонард Эйлер доказал (попробyte и здесь свои силы), что все четные совершенные числа имеют вид, указывающий Евклидом. Таким образом, вопрос, конечно или бесконечно множество четырех совершенных чисел, свелся к вопросу, конечно или бесконечно множество простых чисел Мерсенна, то есть к вопросу, реализует формула (8) нашу программу-minимум. Ответ на этот вопрос не известен до сих пор *).

Формула (9) также не всегда дает простые числа, например, если $n$ имеет простой нечетный делитель $m$, то $p$ делится на $2^{m/2} + 1$, а если $n$ само нечетно, то $p$ делится на 3. Таким образом, вместо $n$ в формулу (9) имеет смысл подставлять только 0 и степень числа 2. При $n=0, 2^0, 2^1, 2^2, 2^3$ и $2^4$ формула (9) действительно дает простые числа, и Пьер

*) Об истории и современном состоянии исследовании по совершенным числам и простым числам Мерсенна вы можете прочитать в статье И. Я. Депмана, «Квант», 1971, № 8.

Форма, живший в XVII века, высказал предложение, что и при любом $n$ вида $2^k$ формула (9) дает простое число; в его числе простые числа вида $2^{2k} + 1$ получили название чисел Ферма. Гипотезу Ферма опроверг Эйлер, указывающий, что число $2^{25} + 1$ делится на 641. В настоящее время известно несколько значений $n$ вида $2^k$, при которых по формуле (9) получаются составные числа, но не найдено ни одного нового простого числа Ферма, отличного от указанных выше.

Простые числа Ферма обнаруживают неожиданную связь с геометрией. Выдающийся немецкий математик Карл Фридрих Гаусс доказал, что правильный $p$-угольник можно построить циклелем и линейкой при простом $p$ в том и только том случае, когда $p$ — число Ферма*). Более общий результат таков: правильный $m$-угольник допускает построение циклелем и линейкой тогда и только тогда, когда $m=2^s \cdot p_1p_2 \dots p_l$, где $p_1, p_2, \dots, p_l$ — попарно различные простые числа Ферма.

Скатерть Улама

Формулы (8) и (9) содержат возведение в степень. А нельзя ли задания бесконечного многохиспель объятиться лишь сложением, вычитанием и умножением? Поищем ответ на этот вопрос.

Начнем с рассмотрения многочленов от одной переменной с натуральными коэффициентами; посмотрим, какие многочлены будут свойствами и в каком количестве.

Возьемем вначале многочлены первой степени (то есть линейные многочлены). Очевидно, что приведенный многочлен $x$ задает бесконечного многочленных чисел, более того, все простые числа, но это неинтересный случай. А что можно сказать о многочлене $ax + b$ (где $a, b$ и $x$ — натуральные числа)? Ясно, что если $a$ и $b$ имеют общий делитель, отличный

*) Подробнее об этом открытии тогда ещесовсем молодного Гаусса расссказано в статье С. Г. Гиндикна, «Квант», 1972, № 1.

8

Рис. 1.

от 1, то значение многочлена $ax + b$ — число составное, кратное этому делителью. Случай же, когда $a$ и $b$ взаимно просты, гораздо менее оцениден.

Французский математик Лежандр (живший в XVIII веке) высказал гипотезу, что если $a$ и $b$ взаимно просты, то в арифметической программе с первым членом $b$ и разнотою $a$ встречается бесконечно много простых чисел. Эта гипотеза была доказана лишь в прошлом столетинемецим математиком Леженом Дирихле.

Перейдем теперь к квадратным многочленам. Среди них есть «рекордсмены», например, многочлен $x^2 + x + 41$ — его изучал еще Леонард Эйлер. Этот многочлен принимает простые значения при $x = 1,2,...,40$. При $x=41$ его значение — составное.

Доказано, что никакой многочлен (отличный, разумется, от конструкты) не может иметь в качестве значений только простые числа, но до них пор не извесно, существует ли многочлен (кроме линейного), среди значений которого встречается бесконечно много простых чисел.

9

Прис. 2

Прис. 3.

Интерес к представлению простых чисел в виде значений квадратных многочленов недавно возникли в связи с необходимым наблюдением С. М. Улама*). Начав на спирали из всех натуральных чисел (рис. 1) отмечать простые числа, Улам с удивлением обнаружил, что простые числа выстраивают по диагоналям, образуя довольно длиные цепочки. (Доказите, что числа, расположенные вдоль какой-либо диагонали в пределах, ограниченных на рисунке 1 красными линиями — это значения некоторого квадратного многочлена с целыми коэффициентами). Еще более удивительным оказалось то, что закономерность эта наблюдалась и тогда, когда спираль была продолжена (с помощью ЭВМ) до больших чисел — на рисунке 2 светлими точками отмеченены простые числа на спирали из первых 10 000 чисел. Узор, изобранный на рисунке 2, получил название «скатерть Улама».

Чтобы отмеченная закономерность проявилась, не обязательно начинать спираль с единицей. Например, значения многочлена $x^2 + x + 41$ выстраиваются по диагоналям у спирали, начинаяшейся с числа 41 (рис. 3). Возможно, что читатели «Кванта», проявив изобретательность и должное терпение, смогут найти новые красные «геометрические» закономерности расположения простых чисел среди многочеств всех чисел.

Феномен со стремлением простых чисел располагается в цепочки вдоль диагоналей был обнаружен сравнительно недавно и еще не получил какого-либо математического объяснения.

О представлении простых чисел с помощью многочленов от многих переменных мы сказем в конце статьи.

Экспоненциальный многочлен Джулии Робинсон

Экспоненциальные многочлены отличаются от обычных тем, что в них показатели степени могут быть не только конкретные натуральные числа, но и линейные многочлены от переменных с натуральными коэффициентами, то есть многочлены вида $a_1x_1 + a_2x_2 + \ldots + a_kx_k + b$, где $a_1, a_2, \ldots, a_k, b$ — целые неотрицательные числа.

Простейшим примерами экспоненциальных многочленов от переменной $n$ являются правила части формул (8) и (9).

В дальнейшем мы всегда будем представлять, что все встречшиеся у нас переменные принимают целые положительные значения.

В 1952 году американский математик Джулия Робинсон*) опубликовала следующий результат:

*) Так было сделано это наблюдание, красочно рассказывает М. Гарднер в «Matематических досугах», М., «Мир», 1972.

10

Существует экспоненциальный многочлен $R(x_0, \dots, x_h)$, такой, что любое его положительное значение при целых положительных значениях переменных является простым числом; любое простое число можно представить в маком виде.

В результате получается такая «формула для простых чисел»:

$$p = R(x_0, \dots, x_h).$$

Эта формула заменяется вот чем. Во-первых, в нее входят только целые числа, и потому, в отличие от формул Миллса, Райта и им подобных, формула Джулии Робинсон может быть выписана явно. Во-вторых, она задает все простые числа, а не только какие-то избранные из них, в отличие от всех рассмотренных выше формул. В-третьих, хотя формула (10) задает и не только простые числа, у нас есть очень простой способ отсеивания «лишних» чисел: каждое не простое значение $R$ при целых положительных значениях неизвестных не преводходит нуля. Этим формула Джулии Робинсон выгодно отличается от формул (8) и (9), а также и от только что рассмотренных полномomialных формул *).

Доказательство Джулии Робинсон совершено элементарно. Ниже излагаются его основные идеи; доведение же доказательства до формальной строгости мы оставляем читателя: все промежутные результаты формулированы в виде пятей лемм, — их-то и нужно доказать. Как мы увидим, из этих лемм следует не только существование экспоненциального многочлена $R$, но и его явный вид.

Что мы должны сделать?

Чтобы доказать теорему Джулии Робинсон, мы, очевидно, должны указать экспоненциальный многочлен $R$, такой, что уравнение (10) разрешимо

*) Полномomialная формула — это формула, задаваемая многочленом.

в натуральных числах относительно переменных $x_0, \dots, x_h$ тогда и только тогда, когда выполнен следующее условие:

$$p - \text{простое число.}$$

Это — пример условия на переменное $p$.

Приведем еще несколько примеров условия на набор переменных:

$$\lambda_1, \dots, \lambda_n, x_0, \dots, x_h.$$

Если мы потребуем, чтобы набор чисел (11) удовлетворял системе уравнения вида

$$F_i(\lambda_1, \dots, \lambda_n, x_0, \dots, x_h) = 0$$

($i=1, \dots, s$), (11’')

или допустим словесное описание типа: «все $\lambda_i$ — простые числа», или «$\lambda_1$ — простое число, $ax_0, \dots, x_h$ — целые числа» и т. д., то тем самым мы из множества в сех наборов (11’’) выделим некоТОрые, подчиняющие наложению на них условия.

Мы не станем точно определить, условия какого вида является для нас допустимыми. Приведенное описание примеров уравнений для определения того способ действия, который мы в дальнейшем будем пользоваться.

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

Если все левые части системы уравнения (11’’) являются экспоненциальными многочленами от $\lambda_1, \dots, \lambda_n, x_0, \dots, x_h$, и решения этой системы ищутся в целых положительных числах, то такая система называется экспоненциально диофантовой; если $F_i$ — объIkновенные многочлены, то система уравнения (11’’) называется просто диофантовой.

Уравнение (10) является примером экспоненциального диофантова уравнения относительно переменных $p, x_0, \dots, x_h$.

Мы будем говорить, что две системы уравнений, имеющие одни и те же параметры, эквивалентны другому относительно этих параметров, если множество тех значений параметров, при которых имеем решение одна из этих систем, совпадает со множеством тех значений параметров, при котором имеем решение и другая система. (Обратите внимание, что в этом определении ничего не говоряем.)

11

рится о связи значений неизвестных—для наших целей это неважно, эквивалентные в нашем понимании системы могут вообще не иметь общих неизвестных.)

Приером эквивалентных условий относительно параметра $\lambda$ могут служить неравенство

$$2^n < \lambda < 2^{n+1}$$

и равенство

$$\lambda = (2x_0 + 1) \cdot x_1.$$

Ясно, что каждое из этих условий имеет решение тогда и только тогда, когда параметр $\lambda$ принадлежит множество чисел, не являющихся целыми степени числа 2.

В этой терминологии наша цель формулируется так: найти эквивалентный многочлен $R(x_0, \dots, x_h)$, такой, что условие (10) эквивалентно условию (11) относительно параметра $p$.

Однако требование, чтобы параметр $p$ стоял только в левой части равенства (10), является, как мы сейчас увидим, излишне жестким.

Пусть удовлетворяя такой: найти эквивалентный многочлен $Q(p, x_1, \dots, x_h)$, такой, что эквивалентно диофантово уравнение (условие на $p, x_1, \dots, x_h$)

$$Q(p, x_1, \dots, x_h) = 0$$

(12) эквивалентно условию (11).

Положим

$$R(x_0, \dots, x_h) = x_0 \cdot (1 - Q^2(x_0, \dots, x_h)).$$

Лемма 1. Если эквивалентные многочлены $R$ и $Q$ связаны соотношениям (13), то уравнения (10) и (12) эквивалентны относительно параметра $p$.

Нам достаточно даже найти не уравнение, а хотя бы систему эквивалентного диофантовых уравнений

$$\begin{cases} Q_1(p, x_1, \dots, x_h) = 0, \\ Q_l(p, x_1, \dots, x_h) = 0, \end{cases}$$

эквивалентную условию (11) относительно $p$.

Лемма 2. Если

$$Q(p, x_1, \dots, x_h) = \sum_{i=1}^{l} Q_i^2(p, x_1, \dots, x_h),$$

мо системе (14) эквивалентна уравнению (12).

Именно понском системы эквивалентного диофантову уравнения, эквивалентной условию (11), мы и будем занимать.

Что такое простое число?

Страный вопрос, — удивится читатель. Каждый знает, что простое число — это число, большее единиццы, которое делится только на единицу и на себя. Конечно, это так, но с таким определенным работать нелегко — ведь оно предполагает, что проверка простоты числа состоит в переборе бесконечного числа потенциальных делителей — всех натуральных чисел, кроме 1. Для наших же целей больше подходит следующее определение:

число $p$ является простым, если $p > 1$ и $p$ не делится ни на какое число, меньше $p$ и отличное от 1.

В этом определении нет ограничения $q \neq 1$, и, что более важно, оно позволяет переменное число уравний H.O.Д. (1, $p$) = 1, H.O.Д. (2, $p$) = 1, …, H.O.Д. (p - 1, $p$) = 1 свести в одно условие:

H.O.Д.((p - 1)!, $p$) = 1.

Сделанное замечание позволяет нам написать первую систему уравнения, эквивалентную условию (11) относительно параметра $p$:

$$\begin{cases} p = r + 1, \\ s = r!, \\ H.O.Д. (s, p) = 1. \end{cases}$$

Первое из этих условий имеет исключый вид эквивалентного диофантова (более того, диофантова) уравнения, а третье легко приводится к таким же виду за счет введения двух новых неизвестных:

*) H.O.Д. (a, b) — это наиболее общий делитель чисел $a$ и $b$.

12

Лемма 3. Условие (17) эквивалентно относительной параметров $r$ и $s$ условия

$$x_1 \cdot s - x_2 \cdot p = 1^*).$$

Так как уравнение (18) экспоненциально диофантово, то нам осталось лишь найти систему экспоненциально диофантовых уравнений, эквивалентную относительной параметров $r$ и $s$ условия (16).

Как вычислить факторial?

В условия (16) входит $r!$; этот-то факторial и «мешает» нам. Вспомним, что факторial функирует в выражении для биомпальных коэффициентов**): при $t \geq r$

$$C_t^r = \frac{t(t-1) \dots (t-r+1)}{r!},$$

то есть

$$r! = \frac{t(t-1) \dots (t-r+1)}{C_t^r}.$$

Многочлен, стоящий в числитель, имеет довольно сложную структуру. Попытаемся заменить его более простым—a именно, многочленом $t^r$. При $t \geq r$ имеем:

$$\frac{t^r}{C_t^r} = \frac{t^r}{t(t-1) \dots (t-r+1)} \times \frac{t(t-1) \dots (t-r+1)}{C_t^r} = \left(1 + \frac{1}{t-1}\right)\left(1 + \frac{2}{t-2}\right) \times \dots \times \left(1 + \frac{r-1}{t-r+1}\right) \cdot r! \geq r!.$$

Легко видеть, что

$$r! = \lim_{t \to \infty} \frac{t^r}{C_t^r},$$

(*) Сравните эту лемму с леммой 2 из «Кванта» № 6 за 1972 год, с. 33.

**) О свойствах биомпальных коэффициентов «Кванта» рассказывал недократно; см., например, № 6 за 1970 год, с. 17—25, или № 2 за 1973 год, с. 27—34.

однако эта запись факторила нам ничего не дает, поскольку $t$, будучи параметром в исходной системе уравнений, может принимать любые, сколько угодно больше, но конечные значения. Но мы и не будем переходить к предлу, а воспользовемся целочисленностью $r!$ — из (19) и (20) следует, что при достаточно больших $t$

$$r! = \left[ \frac{t^r}{C_t^r} \right].$$

Лемма 4. Формула (21) верна как молоко $t \geq 2 r^{r+2}$.

Лемма 4 позволяет преобразовать условия (16) в эквивалентную ему относительно параметров $r$ и $s$ системы (проверьте эквивалентность!)

$$\begin{cases} t = 2r^{r+2}, \\ c = C_t^r, \\ t^r = s \cdot c + (x_3 - 1), \\ (x_3 - 1) + x_4 = c. \end{cases}$$

Здесь условия (22), (24) и (25) имеют требуемый вид, и нам остается лишь найти систему экспоненциально диофантовых уравнений, эквивалентных условия (23) относительно параметров $r$, $t$ и $c$.

Итак, нам осталось «избавиться» от биомпального коэффициента.

Биомпальные коэффициенты — это коэффициенты биома!

Только что мы использували выражение биомпальных коэффициентов через факторial; но биомпальные коэффициенты имеют много и других определений. Воспользовемся теперь, что

$$(u + 1)^t = \sum_{i=0}^{t} C_t^i u^i.$$

Эта формула является определением биомпальных коэффициентов, если рассматривается как мождество относительно $u$. Но нам нужно, чтобы $u$ было неизвестной, принимающей в качестве конкретином решении исходной системы лишь одно значение.

13

Заметим, что
$$C_t^i \leq \sum_{i=0}^{t} C_t^i = (1+1)^t = 2^t,$$
и, таким образом, если
$$u > 2^t,$$
то $C_t^0, C_t^1, \dots, C_t^t$ — это цифры в записи числа $(u+1)^t$ в позиционной системе числения с основанием $u$.
Следовательно, биомпальные коэффициенты однозначно определяются тем условием, что равенство (26) и неравенства (27) и (28) одновременно выполнены хотя бы при одном значении $u$.

Лемма 5. Условие (23) эквивалентно относительной параметров $r, t$ и $c$ системы условия
$$\begin{cases} u = 2^t + 1, \\ x_5 = u + 1, \\ x_5^t = x_6 u^{r+1} + cu^r + x_7, \\ x_7 + x_8 = u^r, \\ c + x_9 = u. \end{cases}$$

Здесь все условия уже имеют необходимый нам вид.

Итак, мы показали, что условия (11) эквивалентно относительной параметра $p$ системе, состоящий из экспоненциального диофантовых уравнений (15), (18), (22), (24), (25), (29) — (33). Чтобы получить требуемый экспоненциальный многочлен, осталось переменовать переменные $r, s, t, c$ и $u$ в $x_{10}, x_{11}, x_{12}, x_{13}, x_{14}$, объединить по лемме 2 все уравнения в одной и преобразовать по лемме 1 это уравнение к использованию виду (10).

Дальнейшие шаги
Формула (10) не содержит явно номера задаваемого его простого числа. Описанный выше способ построения экспоненциального многочлена $R$ не дает прямого пути для включения номера простого числа в формулу (10). Используя существенно более сложную технику, Мартин Дейвис, Хилэри Патnam и Джуляя Робинсон в 1961 году доказали одну очень сильную теорему, которая имеет такое с ледств и е.

Существует экспоненциальный многочлен $P(x_0, \dots, x_k, n)$ макой, что при каждом фиксированном значении параметра $n$ и произвольных значениях остальных переменных, многочлен $P$ принимает одно положительное значение, и этим значением является $n$-е простое число.

В 1970 году автор этой статьи удалось использовать другие результаты Джулия Робинсон, построить такое диофантовую равенение:
$$M(a, b, c, z_1, \dots, z_m) = 0,$$
(34) которое разрешимо тогда и только тогда, когда параметры $a, b$ и $c$ связаны соотношением $a = b^c$. Этот результат позволяет осуществить в формулировке предыдущей теоремы слово «экспоненциальный», то есть позволяет построить многочлен, заданной простые числа. Об этом, однako, мы поговорим в другой раз. Те же читатели, кого заинтересовала подобная тематика и кого не страшат трудности, могут попробовать самостоятельно разобраться в статье автор «Диофантовы многочества», опубликованной в журнале «Успех математических наук», XXVII, № 5, 1972 год.

Темы для размышлений

1. Докажите, что варифметических прогрессиях 3, 7, 11, . . . и 5, 11, 17, . . . бесконечно много простых чисел.
2. Каково множество тех многочленов, значения которых лежат вдоль диагонали, если спираль (см. с. 9) начата с 1? с некоторого числа $u$? с некоторого числа $u$, и по спирали стоит член арифметической прогрессии $u, u + v, u + 2v, \dots$?
3. Теорема Вильсона утверждает, что если $p$ — простое число, то $(p-1)! + 1$ делится на $p$. Как можно использовать этот результат, чтобы уменьшить число неизвестных в экспоненциальном многочлене $R$, заданной простые числа?
4. Постройте экспоненциальный многочлен $S(x_0, \dots, x_h)$, который задает множество получим простых чисел-близнецов, то есть такой, что если $S(x_0, \dots, x_h) > 0$, то оба числа $S(x_0, \dots, x_h) - 1$ и $S(x_0, \dots, x_h) + 1$ являются простыми, и наоборот, если $s-1$ и $s+1$ простые числа, то $S(x_0, \dots, x_h) = s$ при некоторых $x_0, \dots, x_h$.
5. Постройте экспоненциальный многочлен $T(q, x_0, \dots, x_m)$, такой, что если $q$ — простое число, то существует числа $x_0, \dots, x_m$ такие, что $T(q, x_0, \dots, x_m) > 0$;
   если $q$ — простое число и $T(q, x_0, \dots, x_m) > 0$, то $T(q, x_0, \dots, x_m)$ — простое число, следующего за $q$;
   если $q$ не является простым числом, то всегда $T(q, x_0, \dots, x_m) \leq 0$.

Этот экспоненциальный многочлен дает «формулу для следующей простого числа».