Бесконечность простых через функцию Эйлера [Теория чисел]

[venco]

Спасибо, теперь понятно.
Надо бы ещё удостовериться, что вывод формулы Эйлера не использует косвенно бесконечность множества простых чисел.

[Whitaker]

Нет вроде не использует.
Если $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$, то

$$\varphi(n)=n\prod \limits_{j=1}^{k}\left(1-\dfrac{1}{p_j}\right)$$

[Null]

Китайская теорема об остатках и комбинаторика, не используют количество простых чисел.
Ну или формула включения-исключения.

[ewert]

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

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

Не использует. Но он существенно сложнее, чем сама бесконечность. Отсюда и абсурдность ситуации.

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

А зачем туда прибавлять еще единичку?

Затем, что полученное после этого число будет заведомо простым и заведомо новым, и это очевидно. А кроме очевидности -- это ещё и стандартно.

[venco]

ewert в сообщении #722037 писал(а):

полученное после этого число будет заведомо простым

Не совсем. Правильно - будет содержать новый простой множитель.

[ewert]

(Оффтоп)

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

Не совсем. Правильно - будет содержать новый простой множитель.

Совсем, т.к. составное число делится на хоть одно простое, не совпадая с ним. Впрочем, это уже вопрос фразеологии (или, что то же, ловля блох).

[vorvalm]

Для доказательства бесконечности простых чисел можно использовать
функцию Эйлера в другом плане.
Т.к. функция Эйлера определяет число чисел, взаимно простых с модулем
и взаимно несравнимых по модулю, то, расположив их в порядке возрастания,
получим приведенную систему положительных вычетов, не превышающих модуль $p_k\#.$
Первым вычетом ПСВ будет число 1, ну а вторым будет число $p_{k+1}$ и
далее будут располагаться последовательные простые числа вплоть до числа $p_{k+1}^2$