2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
01/01/18 20:50 UTC: Перешли на HTTPS в тестовом режиме. О проблемах пишите в ЛС cepesh.



Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Функция Эйлера больше числа делителей при n>30
Сообщение26.03.2015, 16:05 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение26.03.2015, 16:19 


26/08/11
1676
Пусть $n=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}$

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

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение26.03.2015, 16:24 


06/12/14
510
Shadow в сообщении #995972 писал(а):
Пусть $n=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}$

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

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

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение26.03.2015, 16:27 


26/08/11
1676
Можно

(Оффтоп)

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

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение26.03.2015, 16:28 
Аватара пользователя


12/05/12
604
Оттуда
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?

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение26.03.2015, 16:55 


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

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

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение26.03.2015, 17:00 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение26.03.2015, 17:04 


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

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение26.03.2015, 17:16 


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

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение26.03.2015, 17:33 


18/08/08
157
unistudent в сообщении #996004 писал(а):
можно привести пример такого $16<n< 30$, для которого значения функции Эйлера $\varphi (n)$ меньше, чем число делителей числа $n$?


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

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение26.03.2015, 18:14 
Аватара пользователя


12/05/12
604
Оттуда
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$.

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение26.03.2015, 19:49 


26/08/11
1676
cool.phenon, я спросил
Shadow в сообщении #995995 писал(а):
когда $k+1\ge p^k-p^{k-1}$
При каких $k$ и при каких $p$ это возможно.
Я не говорил что никогда. Иначе и задачи не было бы. Таких случаев очень мало, слесарь на пальцах одной руки посчитает.
cool.phenon в сообщении #996028 писал(а):
Такой метод доказательства не пройдёт, если я правильно понял мысль
Пройдет и докажете почему именно $30$.

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение27.03.2015, 02:05 
Аватара пользователя


12/05/12
604
Оттуда
Shadow

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

 Профиль  
                  
 
 Re: Функция Эйлера
Сообщение27.03.2015, 08:27 


26/08/11
1676
$\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, или меньше либо равно, но в степени, компенсирует эту двойку.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group