Интересная задача о НОД ...

[Джек]

Существует ли такое натуральное число n што выполняется равенство:
НОД(n,1)+НОД(n,2)+...+НОД(n,n)=2009n?

[Руст]

Пусть $gcd(n,k)=\frac nd$ таких значений $\phi(d)$. Поэтому уравнение эквивалентно
$G(n)=\sum_{d|n} \frac{\phi (d)}{d} =2009$.
Так как суммируется по делителям d мультипликативная функция, то итоговая функция $G(n)$ так же мультипликативна. $G(p^k)=\frac{1+(k+1)(p-1)}{p}$. Разлагая $2009=7*7*41$ находим.
Если p минимальный простой делитель числа n, то он останется в знаменателе за исключением случая $p|k$. В последнем случае $G(p^{mp})=m(p-1)+1$.
Одним из решений является $m(p-1)=2008$ (так находятся все решения n являющиеся степенью простого числа). Соответственно $n=2^{4016},3^{3012},5^{2560},503^{2012}.$

[Джек]

спасибо...

[maxal]

Руст в сообщении #186166 писал(а):

Если p минимальный простой делитель числа n, то он останется в знаменателе за исключением случая $p|k$.

Это неверно.
Например, $n=2^4 3^{1003}$ также является решением.

[Руст]

maxal писал(а):

Руст в сообщении #186166 писал(а):

Если p минимальный простой делитель числа n, то он останется в знаменателе за исключением случая $p|k$.

Это неверно.
Например, $n=2^4 3^{1003}$ также является решением.

Что же неверно, $2|4$?
Я не стал искать все решения, а нашёл только вида $p^k$. Хотя можно было найти все.

[maxal]

Руст
Твое утверждение о том, что наименьшее простое должно делить свою степень, неверно.
Только мой пример неудачным вышел. Вот новый, опровергающий твое утверждение: $n=3^{16} 5^{214}.$

[Руст]

Согласен. Когда минимальное простое не 2, оно может сокращаться и как делитель $1+k(p-1$ для другого простого p. Но я ограничился случаем, когда других простых делителей нет.

[Джек]

так в умове спрашывалось ,существует ли такое...??? Руст показал што существует...

[maxal]

Джек в сообщении #186214 писал(а):

так в умове спрашывалось ,существует ли такое...??? Руст показал што существует...

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

Руст в сообщении #186190 писал(а):

Я не стал искать все решения, а нашёл только вида $p^k$. Хотя можно было найти все.

Ну все не надо, а вот найти минимальное решение - интересная задачка.

[Руст]

Компьютерных расчётов не делал. Расчёты в ручную с помощью калькулятора дали пока минимальное $n=2^4*3^2*5^2*7^2*11^3*13^3*19^2=186 214 671 442 800$.