Бесконечность простых чисел [Теория чисел]

[Whitaker]

Здравствуйте, уважаемые друзья!

Доказать бесконечность числа простых чисел, подсчитывая число чисел, не превосходящих $N$, в каноническое разложение которых не входят простые числа, отличные от $p_1, p_2, \dots, p_k$

Честно говоря, не знаю вообще с чего начать.
Подскажите пожалуйста.

С уважением, Whitaker.

[DjD USB]

От противного...Пусть простых чисел не бесконечно много....

[ИСН]

Зачем нам противный? Смотрите. Сколько существует степеней $p_1$, не превосходящих $N$?

[Whitaker]

DjD USB
Мне кажется, что метод от противного вообще не нужен тут

[nnosipov]

Whitaker в сообщении #634659 писал(а):

Честно говоря, не знаю вообще с чего начать.

Если $p_1^{\alpha_1} \ldots p_s^{\alpha_s} \leqslant N$, то $\alpha_1 \leqslant $ чего?

[bot]

Дык, если я верно понял, противное уже предположено и приведён полный список простых. Далее для каждого $N$ предлагается оценить число решений неравенства $p_1^{x_1}\ldots p_s^{x_s}\leqslant N$.
Их будет не больше, чем число решений уравнения $x_1+\ldots +x_s+x_{s+1}=[\log_2N]$.

-- Вт окт 23, 2012 18:02:52 --

Ну да - не надо жадничать с оценками, можно значительно грубее.

[nnosipov]

Действительно, не жадничайте. Каждый из $\alpha_i$ попросту не превосходит этого самого.

[Whitaker]

nnosipov в сообщении #634689 писал(а):

Whitaker в сообщении #634659 писал(а):

Честно говоря, не знаю вообще с чего начать.

Если $p_1^{\alpha_1} \ldots p_s^{\alpha_s} \leqslant N$, то $\alpha_1 \leqslant $ чего?

$N\geqslant p_1^{\alpha_1}\dots p_s^{\alpha_s}>2^{\alpha_1}$
Отсюда получаем, что $\alpha_1<\log_2 N$ или $\alpha_1\leqslant [\log_2 N]$
Верно?

[nnosipov]

Ну, делайте выводы. Остались сущие пустяки.

[Whitaker]

Мысль уловить не могу никак

[nnosipov]

Сколько существует наборов $(\alpha_1,\dots,\alpha_s)$ целых неотрицательных показателей, если каждый показатель не превосходит некоего $m$?

[ИСН]

Погодите с наборами.

ИСН в сообщении #634686 писал(а):

Сколько существует степеней $p_1$, не превосходящих $N$?

-- Вт, 2012-10-23, 16:11 --

А, это Вы уже по сути сделали:

Whitaker в сообщении #634702 писал(а):

$\alpha_1\leqslant [\log_2 N]$

-- Вт, 2012-10-23, 16:12 --

Ну тогда да - наборы. Первая альфа может принимать вот столько-то разных значений. Вторая - столько. А вместе..?

[bot]

Ну, для чего оценки делались? Если список простых полный, то сколько чисел от 1 до N, а из них составных?

(Оффтоп)

nnosipov в сообщении #634701 писал(а):

Действительно, не жадничайте

А меня моя жадность до формулы Стирлинга довела

[nnosipov]

Вспомните, как получается формула для числа делителей. Здесь та же история.

[Whitaker]

nnosipov
Ну вот смотрите если $N=50$ рассмотрим $p_1=2, p_2=3$
Рассмотрим $2^{\alpha}3^{\beta}\leqslant 50$
Исходя из тех же соображений можно сказать, что $\alpha, \beta \leqslant [\log_2 50]=5$
Но ведь уже $3^5>50$ или я Вас неправильно понял?

-- Вт окт 23, 2012 15:15:54 --

nnosipov в сообщении #634719 писал(а):

Сколько существует наборов $(\alpha_1,\dots,\alpha_s)$ целых неотрицательных показателей, если каждый показатель не превосходит некоего $m$?

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