Функция Эйлера [Теория чисел]

[Whitaker]

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

Доказать, что

$$\dfrac{a}{\varphi(a)}=O(\ln\ln a).$$

Моя попытка решения: Раз у нас число $a>1$, то это число можно разложить на множители $a=q_1^{\alpha_1}q_2^{\alpha_2}\dots q_s^{\alpha_s}$, где $\alpha_i\geqslant 1$ и $q_1<q_2<\dots<q_s$
Пусть $p_1, p_2, p_3, \dots$ - последовательные простые числа. Очевидно, что $q_1\geqslant p_1, q_2\geqslant p_2, \dots, q_s\geqslant p_s$.
Получаем следующие очевидные неравенства:

$$0<\dfrac{a}{\varphi(a)}=\prod_{i=1}^{s}\left(1-\dfrac{1}{q_i}\right)^{-1}\leqslant \prod_{p\leqslant p_s}\left(1-\dfrac{1}{p}\right)^{-1}=C\ln p_s+O(1).$$

Здесь конечно неравенство с символом О-большое немного нехорошо смотрится, но это не важно. Если показать, что $p_s=O(\ln a)$, то все отлично. Самый главный вопрос, а как именно его и получить?
Помогите пожалуйста.

[Sonic86]

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

Здесь конечно неравенство с символом О-большое немного нехорошо смотрится, но это не важно.

Нормально смотрится.

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

Если показать, что $p_s=O(\ln a)$, то все отлично. Самый главный вопрос, а как именно его и получить?

Оцените $s$.
Для ясности может быть полезно найти пару чисел $n$ таких, что $\frac{n}{\varphi(n)}$ максимально на $[1;n]$.

[ex-math]

Вы уже показали, что $a\geqslant p_1\ldots p_s$, а это произведение есть экспонента от функции Чебышева $\theta(p_s)$. Ее нижняя оценка Вам известна.

[Whitaker]

ex-math
Действительно, $a\geqslant p_1p_2\dots p_s$ и так как $\theta(p_s)=\ln(p_1p_2\dots p_s)$, тогда

$$e^{\theta(p_s)}\leqslant a$$

Я знаю верхнюю оценку для $\theta(x)$ и $\psi(x)$. Например, $\theta(x)\leqslant\psi(x)<2x$
Нижние оценки я что-то не видел

[ex-math]

Вы знаете нижнюю оценку $\psi(x)$.
Остается показать, что $\psi(x)-\theta(x)$ мала. Это нетрудно, потому что главные слагаемые в этой разности пропадут.

[Whitaker]

Ну знаю вроде такую оценку $\psi(x)>(x-2)\ln 2-\ln(x+1)$
Ну $\psi(x)-\theta(x)=\theta(x^{1/2})+\theta(x^{1/3})+\dots$
Как они пропадут?

[ex-math]

Можно так:

$$ \theta(x^\frac12)+\theta(x^\frac13)+\ldots=\sum_{2\leqslant k\leqslant\frac{\ln x}{\ln 2}}\sum_{p\leqslant x^\frac1k}\ln p=\sum_{p\leqslant x^\frac12}\ln p\sum_{2\leqslant k\leqslant\frac{\ln x}{\ln p}}1\leqslant\sum_{p\leqslant x^\frac12}\ln p\,\cdot\frac{\ln x}{\ln p}\leqslant\pi(x^\frac12)\ln x. $$

-- 30.11.2012, 13:28 --

Да и просто, без всякой возни

$$ \theta(x^\frac12)+\theta(x^\frac13)+\ldots<2x^\frac12\,\frac{\ln x}{\ln 2}, $$

пользуясь Вашей верхней оценкой для $\theta(x)$ и тривиальной для их количества $x^\frac1k\geqslant2$, т.е. $k\leqslant\frac{\ln x}{\ln 2}$. Это все было ожидаемо, потому что $\theta(x)$ сократилась, а оставшиеся не больше всего лишь корня из $x$. Еще отсюда следует, что $\theta(x)\sim\psi(x)$.

[Whitaker]

ex-math
Вы доказали, что $\psi(x)-\theta(x)\leqslant \pi(\sqrt{x})\ln x$. По теореме Чебышева об оценке $\pi(x)$ при достаточно большом $x$ имеем:

$$\pi(\sqrt{x})\ln x\leqslant A\dfrac{\sqrt{x}}{\ln{\sqrt{x}}}\ln x=2A\sqrt{x}=B\sqrt{x}$$

Отсюда получаем, что $\theta(x)\geqslant \psi(x)-B\sqrt{x}>(x-2)\ln 2-\ln(x+1)-B\sqrt{x}$
Поменяв аргумент на $p_s$ получаем:

$$\theta(p_s)>(p_s-2)\ln 2-\ln(p_s+1)-B\sqrt{p_s}>(p_s-2)\ln 2-p_s\dfrac{\ln 2}{4}-p_s\dfrac{\ln 2}{4}>p_s\dfrac{\ln 2}{2}-2>\dfrac{p_s}{8},$$

т.е. неравенство имеет место при достаточно большом $p_s.$
У нас ведь $a>\exp(\theta(p_s))>\exp(\frac{p_s}{8}),$ тогда $p_s<8\ln a$.
В итоге получаем:

$$0<\dfrac{a}{\varphi(a)}<\prod _{p\leqslant p_s}\left(1-\dfrac{1}{p}\right)^{-1}\leqslant K\ln p_s<8K\ln\ln a$$

Из последнего вытекает, что $\dfrac{a}{\varphi(a)}=O(\ln \ln a)$
Верно?

[Sonic86]

(Оффтоп)

суровые какие методы. Я оценки $s=O\left(\frac{\ln x}{\ln_2 x}\right)$ руками доказываю, сравнивая $p_1...p_s$ с $s!$. Хотя с другой стороны, еще раз с $\theta, \psi$ повозиться полезно.

[Whitaker]

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

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

Если показать, что $p_s=O(\ln a)$, то все отлично. Самый главный вопрос, а как именно его и получить?

Оцените $s$.
Для ясности может быть полезно найти пару чисел $n$ таких, что $\frac{n}{\varphi(n)}$ максимально на $[1;n]$.

Sonic86 мне также интересно порешать Вашим методом.
А зачем нужно находить максимум $\dfrac{n}{\varphi(n)}$ на $[1;n]?$ Что-то пока не понимаю
Я же хочу показать, что $p_s=O(\ln a)$

[ex-math]

Все правильно, только константы я не проверял. Не люблю их вычислять, $O$ получили -- и хватит

То, что предлагает Sonic86 -- это прямое получение оценки $\theta(x)$. Мы же свели к уже полученной оценке $\psi(x)$. И нам нужно не $s$, а $p_s$, то есть если получить оценку $s$, то надо еще будет пользоваться оценками $p_s$.

[Whitaker]

ex-math
Спасибо большое Вам за помощь и за ценные подсказки!
Также благодарю Sonic86 за постоянную помощь!