Функция Эйлера больше числа делителей при n>30

[cool.phenon]

Необходимо показать, что при $n> 30$ значения функции Эйлера $\varphi (n)$ строго больше, чем число делителей числа $n$. Задача вроде бы из лёгких, но никакой идеи даже нет. Помогите, пожалуйста, разобраться.

[Shadow]

Пусть $n=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}$

Чему равна функция Эйлера и чему равно число делителей?

[unistudent]

Shadow в сообщении #995972 писал(а):

Пусть $n=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}$

Чему равна функция Эйлера и чему равно число делителей?

Разве можно сказать что-нибудь о числе делителей из этой записи?

[Shadow]

Можно

(Оффтоп)

Там, конечно не то $n$ - нижний индекс - другая буква

[cool.phenon]

unistudent
Да, можно. $N=(k_1+1)(k_2+1)...(k_p+1)$

-- 26.03.2015, 16:44 --

Shadow
Допустим, выписали.

$$p_1^{k_1}...p_s^{k_s} \prod\limits_{p_i}\left(1-\frac{1}{p_i}\right)>(1+k_1)...(1+k_s) $$

Сразу вопрос: чем здесь так примечательно число 30?

[Shadow]

Нет, я имел ввиду выписать в явном виде функцию Эйлера. Она мультипликативна: Если $\gcd(a,b)=1 \Rightarrow\varphi(ab)=\varphi(a)\varphi(b)$. Если $p$ - простое, то $\varphi(p^a)=p^a-p^{a-1}$.

И тогда чему равно $\varphi(n)$? Используя каноническое разложение $n$

[cool.phenon]

Shadow
Так в левой части неравенства и так явная запись, если вынести все $p_i^{k_i}$ из-под произведения, чтобы они не мешали

[Shadow]

Тогда, сравнивая каждый множитель левой и правой части, можно подумать, когда $(k+1)\ge p^k-p^{k-1}$
При каких $k$ и при каких $p$ это возможно.

[unistudent]

можно привести пример такого $16<n< 30$, для которого значения функции Эйлера $\varphi (n)$ меньше, чем число делителей числа $n$?

[ASH]

unistudent в сообщении #996004 писал(а):

можно привести пример такого $16<n< 30$, для которого значения функции Эйлера $\varphi (n)$ меньше, чем число делителей числа $n$?

Достаточно привести пример числа, где количество взаимно простых чисел с ним будет меньше или равно числа его делителей. Это 24, у него равенство - и тех и этих 8.

[cool.phenon]

Shadow
Такой метод доказательства не пройдёт, если я правильно понял мысль. Возьмём $n=100=5^2\cdot 2^2>30$. Тогда $\varphi(100)=40$. $\varphi(25)=20,\varphi(4)=2$. Если рассмотреть правую часть, то имеем: $\tau(100)=(2+1)\cdot (2+1)$. Если вот в том произведении выше рассмотреть отдельные простые числа и их степени, то $\varphi(100)=\varphi(25)\varphi(4)>3\cdot 3$, и $\varphi(25)>3$, но $\varphi(4)=2<3$. Вернее, он пройдёт, но для каких-то достаточно больших $n$.

[Shadow]

cool.phenon, я спросил

Shadow в сообщении #995995 писал(а):

когда $k+1\ge p^k-p^{k-1}$
При каких $k$ и при каких $p$ это возможно.

Я не говорил что никогда. Иначе и задачи не было бы. Таких случаев очень мало, слесарь на пальцах одной руки посчитает.

cool.phenon в сообщении #996028 писал(а):

Такой метод доказательства не пройдёт, если я правильно понял мысль

Пройдет и докажете почему именно $30$.

[cool.phenon]

Shadow

Ну, допустим, таких случаев $4$ для степеней простых и простых $<30$. Это говорит о том, что если попарно рассматривать скобки из левой и правой частей, то утверждение доказано для всех $n$, которые не делятся на $2,3,4,8$, или делятся, но тогда делятся на $16,32...,9,81.$ итд. Как тогда быть с числами $>30$, которые делятся на $2,3,4,8$?

[Shadow]

$\dfrac{\tau(2)}{\varphi(2)}=2,\;\dfrac{\tau(4)}{\varphi(4)}=\dfrac 4 3,\;\dfrac{\tau(8)}{\varphi(8)}=1,\;\dfrac{\tau(2^k)}{\varphi(2^k)}<1 \;\forall k>3$

$\dfrac{\tau(3)}{\varphi(3)}=1,\;\dfrac{\tau(9)}{\varphi(9)}=\dfrac 1 2,\; \dfrac{\tau(3^k)}{\varphi(3^k)}<\dfrac 1 2 \;\forall k>2$

$\dfrac{\tau(5)}{\varphi(5)}=\dfrac 1 2\cdots$

В отношении $\dfrac{\tau(n)}{\varphi(n)}$ на пользу числа делителей "работает" только двойка, причем только в первой и второй степени, причем максимальньное значение отношения 2.

Присутствие любого простого больше 5, или меньше либо равно, но в степени, компенсирует эту двойку.

Вам просто надо доказать написанное выше, думаю, без проблем.