Простые числа

[xmaister]

Для каждого натурального $n$ найти все простые числа, такие что

$$\sum\limits_{i}p_{i_1}\cdot\ldots\cdot p_{i_{n-1}}-\sum\limits_{i}p_{i_1}\cdot\ldots\cdot p_{i_{n-2}}+\ldots +(-1)^{n-1}<p_1\cdot \ldots\cdot p_n$$

[Sonic86]

Можно пояснить, что в суммах находится, выписав неравенство, например, для $n=3$? А то похоже на $(p_1-1)...(p_n-1)>0$.

[xmaister]

$\sum\limits_{i}p_{i_1}\cdot\ldots\cdot p_{i_{n-1}}=p_2\ldots p_{n-1}+p_1p_3\ldots p_{n-1}+\ldots +p_1\ldots p_{n-2}$

[ИСН]

Стало ещё сильнее похоже на $(p_1-1)...(p_n-1)>0$.

[xmaister]

Как то странно получается... Я подобную штуку получил, когда пытался посчитать количество $a\in\mathbb{Z}/n\mathbb{Z}^{\times}$ не являющихся первообразными корнями. Там вылезала формула включений-исключений. Че-та не пойму так, откуда взялось

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

$(p_1-1)...(p_n-1)>0$.

?

[venco]

xmaister в сообщении #657556 писал(а):

Че-та не пойму так, откуда взялось

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

$(p_1-1)...(p_n-1)>0$.

?

Если в вашем неравенстве всё перенести направо, сумма будет как раз равна вот этому произведению. Т.е. неравенство выполняется для любого, даже пустого, набора простых чисел.

[Sonic86]

xmaister в сообщении #657556 писал(а):

Я подобную штуку получил, когда пытался посчитать количество $a\in\mathbb{Z}/n\mathbb{Z}^{\times}$ не являющихся первообразными корнями.

Что-то я не понял. Вообще-то $\mathbb{Z}/n\mathbb{Z}^{\times}$ циклическая лишь при $n=p^m; 2p^m$ (соответственно, в иных случаях число элементов, не являющихся первообразными, равно порядку группы). В последних случаях число первообразных корней известно. Или я не понял, что Вы ищете?

venco в сообщении #657562 писал(а):

Т.е. неравенство выполняется для любого, даже пустого, набора простых чисел.

даже для просто любых действительных чисел $>1$.

[xmaister]

Sonic86 в сообщении #657563 писал(а):

Вообще-то $\mathbb{Z}/n\mathbb{Z}^{\times}$ циклическая лишь при $n=p^m; 2p^m$

Да, это известно. Пусть $n\in\mathbb{Z}$, положим, что $\varphi (n)=p_1^{\alpha_1}\ldots p_s^{\alpha_s}$. Пусть $A_i$- множество всех $x\in\mathbb{Z}/n\mathbb{Z}^{\times}$, таких что $x^{p_1^{\alpha_1}\ldots p_i^{\alpha_i-1}\ldots p_s^{\alpha_s}}=1$. Ищем $\left|\bigcup\limits_{i=1}^{s}A_i\right|$ по вкл-выкл, тут где-то прокол?

[Sonic86]

xmaister в сообщении #657575 писал(а):

Да, это известно. Пусть $n\in\mathbb{Z}$, положим, что $\varphi (n)=p_1^{\alpha_1}\ldots p_s^{\alpha_s}$. Пусть $A_i$- множество всех $x\in\mathbb{Z}/n\mathbb{Z}^{\times}$, таких что $x^{p_1^{\alpha_1}\ldots p_i^{\alpha_i-1}\ldots p_s^{\alpha_s}}=1$. Ищем $\left|\bigcup\limits_{i=1}^{s}A_i\right|$ по вкл-выкл, тут где-то прокол?

Тааак. Как Вы считали $A_I$? А прокол, думаю, легко обнаружить на примере. Возьмите $n=12$, например. И посмотрите. Что там. И я посмотрю...

[xmaister]

Да, я понял в чем дело, спасибо.

[Deggial]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Помогите решить / разобраться (М)»
Причина переноса: перенес в соответствующий раздел