2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Задача №1 Shortlist-a ММО 2004(Теория чисел)
Сообщение26.01.2007, 17:39 


28/12/05
160
1. Пусть $\tau(n)$- означает число делителей натурального числа $n.$
Докажите, что существують бесконечно много натуральных $a,$ для которых уравнение $\tau(an)=n$ не имеет решения в натуральных числах $n.$

 Профиль  
                  
 
 
Сообщение27.01.2007, 04:37 
Заслуженный участник
Аватара пользователя


11/01/06
3835
Можно взять $a=p^{29}$, $p\geqslant37$-простое.

Добавлено спустя 25 минут 56 секунд:

Док-во основано на 2 наблюдениях:
1) Если уравнение $\tau(an)=n$ не имеет решений, то уравнение $\tau(p^{a-1}n)=n$, $p>a+1$-простое, также не имеет решений (это тривиально).
2) Уравнение $\tau(30n)=n$ не имеет решений (это нудный и скучный перебор).

 Профиль  
                  
 
 
Сообщение27.01.2007, 09:18 
Заслуженный участник


09/02/06
4401
Москва
Если $n=p_1^{k_1}...p_s^{k_s}$, то $\tau(n)=(k_1+1)...(k_s+1)$.
Учитывая это легко проверяется, что работает a=2p, р - нечётное простое число.
1. (n,a)=1, то надо проверить $\prod_i \frac{p_i^{k_i}}{k_i+1} \not =4.$.
Так же рассматриваются случаи
2. (n,a)=2.
3. (n,a)=p.
4. 2p=a|n

 Профиль  
                  
 
 
Сообщение27.01.2007, 09:32 
Заслуженный участник
Аватара пользователя


11/01/06
3835
$\tau(36p)=18$

Добавлено спустя 46 секунд:

($p>3$)

Добавлено спустя 2 минуты 56 секунд:

$\tau(72)=12$

 Профиль  
                  
 
 
Сообщение27.01.2007, 12:27 
Заслуженный участник
Аватара пользователя


07/03/06
2103
Москва
По-моему, верно $\forall n \exists k_1 \forall k>k_1:\tau(n^k)\not = n$. Поэтому, $a=n^{k-1}$

 Профиль  
                  
 
 
Сообщение27.01.2007, 13:29 
Заслуженный участник
Аватара пользователя


11/01/06
3835
Артамонов Ю.Н. писал(а):
По-моему, верно $\forall n \exists k_1 \forall k>k_1:\tau(n^k)\not = n$. Поэтому, $a=n^{k-1}$

$a$ не должно зависеть от $n$. :?

 Профиль  
                  
 
 
Сообщение27.01.2007, 14:34 
Заслуженный участник


09/02/06
4401
Москва
Очевидно, что $\frac{\tau(an)}{\tau(n)}\le \tau(a)$. Поэтому учитывая, что за малым исключением $\frac{n}{\tau(n)}>4$ (быстро растёт), я брал a=pq (произведение двух простых чисел (одно очевидно не годится). Все числа, для которых $\frac{n}{\tau(n)}\le 4$ можно легко перечислить и они дают конечное число исключений, когда не работает a=pq.

 Профиль  
                  
 
 
Сообщение27.01.2007, 15:36 
Заслуженный участник
Аватара пользователя


11/01/06
3835
$\tau(36pq)=36$

Добавлено спустя 44 секунды:

(p,q>3)

Добавлено спустя 3 минуты 52 секунды:

$\tau(72p)=24$
(p>3)

Добавлено спустя 52 секунды:

Таким образом, никакое $a=pq$ ($p\ne q$) не подходит.

 Профиль  
                  
 
 
Сообщение27.01.2007, 17:17 
Заслуженный участник


09/02/06
4401
Москва
Да, вы меня положили на лопатки. Не годится и p=q, так как $\tau(p^29)=9, p\not =3.$
Но работает $a=p^{p-1}$. Если n не делится на p, то $\tau(an)$ делится на p, т.е. не равно n. Если n делится на p, у него должен быть по крайней мере другой простой множитель в степени kp-1 или должен делиться на p^{kp}. В любом случае $\frac{n}{\tau(n)}\ge \frac{2^{p-1}}{p}>p=\tau(a)$ при p>5.

 Профиль  
                  
 
 
Сообщение27.01.2007, 17:37 
Заслуженный участник
Аватара пользователя


11/01/06
3835
Да, так гораздо проще.

 Профиль  
                  
 
 
Сообщение28.01.2007, 09:01 


28/12/05
160
Руст писал(а):
Да, вы меня положили на лопатки. Не годится и p=q, так как
Но работает . Если n не делится на p, то делится на p, т.е. не равно n. Если n делится на p, у него должен быть по крайней мере другой простой множитель в степени kp-1 или должен делиться на p^{kp}. В любом случае при p>5.

Да очень красиво!
Но как же нашли число $p^{p-1}$ или интуиция вам подсказала? :)

 Профиль  
                  
 
 
Сообщение28.01.2007, 10:00 
Заслуженный участник


09/02/06
4401
Москва
student писал(а):
Да очень красиво!
Но как же нашли число $p^{p-1}$ или интуиция вам подсказала? :)

Решений много. Я рассмотрел случай, когда а содержит толькко один простой делитель.
Случаи первой и второй степени легко опровергаются: $\tau(12p)=12, p>3 \ \ \tau(9p^2)=9 \ p\not=3$. Другие степени не пробовал, проще брать степень зависящей от самого р.

 Профиль  
                  
 
 Re: Задача №1 Shortlist-a ММО 2004(Теория чисел)
Сообщение28.01.2007, 10:25 


23/01/07
3516
Новосибирск
student писал(а):
1. Пусть $\tau(n)$- означает число делителей натурального числа $n.$

У меня просьба к участникам данного обсуждения объяснить мне, как начинающему, в чем истинная суть $\tau(n)$?
Имеется в виду, то количество простых множителей, путем произведения которых получено данное число n, т.е. $\tau(1)=0, \tau(3)=1, \tau(5)=1, \tau(3*5)=1+1=2$?

Или я - не о том?

 Профиль  
                  
 
 
Сообщение28.01.2007, 10:35 
Заслуженный участник
Аватара пользователя


11/01/06
3835
$\tau(n)$ - количество натуральных $d$, которые делят $n$, т.е.
$$\tau(n)=\#\{d\in\mathbb{N}\mid d|n\}$$
Если $n=p_1^{\alpha_1}\ldots p_s^{\alpha_s}$ - разложение числа $n$ на простые, то $\tau(n)=(\alpha_1+1)\ldots(\alpha_s+1)$

 Профиль  
                  
 
 
Сообщение28.01.2007, 10:55 


23/01/07
3516
Новосибирск
Красиво выглядит Ваше объяснение, но для меня, по-видимому, пока рано.
А тому, о чем я написал, есть определение? Или это $\alpha$, но зачем тогда при ней единица? Мне кажется, без нее было бы проще.

Хотя, судя по всему, это и не $\alpha$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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