функция Эйлера

[Руст]

Доказать, что для любого натурального m и $\forall \epsilon>0$
существует бесконечно много взаимно простых с m натуральных чисел n, что

$$\phi(2^n-1)<\epsilon 2^n.$$

[Sonic86]

$m$ фиксировано, значит можно брать любое $n$, содержащие делители $p>p_0$
$\frac{\varphi(2^n-1)}{2^n}<\frac{\varphi(2^n-1)}{2^n-1}\leqslant \prod\limits_{p|2^n-1}\left(1-\frac{1}{p}\right)$.
Пусть $p_j,...,p_k$ - последовательные нечетные простые $>p_0$.
Покажем, что можно подобрать $n$ такое, что для любого $t:j\leqslant t\leqslant k$ имеем $p_t\mid 2^n-1$. Возьмем $n=\varphi(p_j...p_k)$. Тогда
$\prod\limits_{p|2^n-1}\left(1-\frac{1}{p}\right)\leqslant \prod\limits_{p_j\leqslant p\leqslant p_k}\left(1-\frac{1}{p}\right)\to 0 \Leftrightarrow \sum\limits_{p_j\leqslant p\leqslant p_k}\frac{1}{p}\to +\infty$, что очевидно при $k\to +\infty, j=C(m)=\operatorname{const}$.

[Руст]

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

Покажем, что можно подобрать $n$ такое, что для любого $t:j\leqslant t\leqslant k$ имеем $p_t\mid 2^n-1$.

Это не верно. Например, если m четно, то n должно быть нечетным, но никакое простое число вида $p=\pm 3 mod 8$ не делит число $2^n-1$ с нечетным n.

[Руст]

Все проходит если брать простые числа вида $p=4km-1$.
Для квадратичного вычета a их порядок (делитель $(4km-2)/2=2km-1$) взаимно прост с m. Если m нечетное и так взаимно прост.
Когда m четно простое вида $p=4km-1=7\mod 8$ и 2 квадратичный вычет.
Из расходимости ряда

$$\sum_{p=-1\mod 4m}\frac 1p$$

расходится и отсюда следует вывод.