теорема евклида

[math84]

Откуда берётся оценка n-ного простого: $p_{n} = 2^{2^{n}}$. Эту оценку я увидел в монографии Ингама Распределение простых чисел. Спасибо.

[ozheredov]

math84
Прибавить один не надо?

[grizzly]

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

В Вашей задаче можете рассуждать по индукции аналогично. Пусть для для всех $k<n_0$ известно, что $p_k<2^{2^k}$. Рассмотрим теперь число $Q=p_1p_2\cdots p_{k}+1$. Очевидно, что $Q<2^{2^{k+1}}$ и оно не делится на все предыдущие простые. Значит, либо оно простое, либо есть ещё простое, меньшее, чем $Q$.

Так достаточно понятно?

[math84]

Всё, теперь понял. Спасибо большое.