Задача №1 Shortlist-a ММО 2004(Теория чисел)

[student]

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

[RIP]

Можно взять $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$ не имеет решений (это нудный и скучный перебор).

[Руст]

Если $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

[RIP]

$\tau(36p)=18$

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

($p>3$)

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

$\tau(72)=12$

[juna]

По-моему, верно $\forall n \exists k_1 \forall k>k_1:\tau(n^k)\not = n$. Поэтому, $a=n^{k-1}$

[RIP]

Артамонов Ю.Н. писал(а):

По-моему, верно $\forall n \exists k_1 \forall k>k_1:\tau(n^k)\not = n$. Поэтому, $a=n^{k-1}$

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

[Руст]

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

[RIP]

$\tau(36pq)=36$

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

(p,q>3)

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

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

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

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

[Руст]

Да, вы меня положили на лопатки. Не годится и 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.

[RIP]

Да, так гораздо проще.

[student]

Руст писал(а):

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

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

[Руст]

student писал(а):

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

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

[Батороев]

student писал(а):

1. Пусть $\tau(n)$- означает число делителей натурального числа $n.$

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

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

[RIP]

$\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)$

[Батороев]

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

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