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

[student]

Функция $\psi$ определяется в множестве натуральных чисел таким образом

$$\psi(n)=\sum_{k=1}^{n}(k,n),\ n\in N,$$

где $(k,n)$- наибольший общий делитель чисел $k$ и $n.$
a) Докажите $\psi(mn)=\psi(m)\psi(n)$ для любого $(m,n)=1, m,n\in N$
б) Докажите, что для каждого $a\in N$ уравнение $\psi(x)=ax$ имеет решения.
в) Найдите всех a\in N для которых уравнение $\psi(x)=ax$ имеет единственное решение.

[RIP]

a)

$$\psi(n)=\sum_{d|n}d\cdot\varphi\left(\frac nd\right),$$

т.е. $\psi(n)$ - свертка мультипликативных функций $n$ и $\varphi(n)$, поэтому мультипликативна.

b) Можно взять $x=2^{2a-2}$

[Руст]

Вычисляя $\psi(p^k)=(k+1)p^k-kp^{k-1}, \ \psi(n)=n\prod_{p|n} (1+ord_p(n)(1-\frrac 1p ))$, получаем, что целое а получается, только если $n=\prod_i p_i^{k_ip_i}, \ a=\prod_i(1+k_i(p_i-1))$.
Так как при р>2 соответствующий множитель нечётен, единственность решения получается, только в случае, когда а степень двойки.