Mathematica competitions in Croatia

For $k=1$, $S(k)=1$. For $k>1$, note that for a positive integer $a<k$ relatively prime to $k$ the number $k-a$ is also relatively prime to $k$. Hence the summands in the sum $S(k)$ can be paired and each pair has sum $k$. The number of positive integers relatively prime to $k$ (and less than $k$) is $\phi (k)$, so $$S(k)=\frac{k\phi (k)}{2}.$$ Let $q$ be the largest prime factor of $m$, and let $2=p_1<p_2<\cdots <p_s=q$ be consecutive prime numbers. Then $m=p_1^{a_1}\dots p_s^{a_s}$ (where some of $a_i$ are 0). We will construct a number $x$ of the form $x=p_1^{b_1}\dots p_s^{b_s}$ satisfying the condition of the problem. Note that $$\begin{array}{rl}2S(x)& =x\phi (x)=p_1^{b_1}\dots p_s^{b_s}\cdot p_1^{b_1-1}(p_1-1)\dots p_s^{b_s-1}(p_s-1)\\ & =p_1^{2b_1-1}(p_1-1)\dots p_s^{2b_s-1}(p_s-1).\end{array}$$ Also, for every $i\le s$ all prime divisors of $p_i-1$ are among $p_1,\dots ,p_s$, so we choose $c_1,\dots ,c_s$ such that $(p_1-1)\dots (p_s-1)=p_1^{c_1}\dots p_s^{c_s}$, i.e. $$2S(x)=p_1^{2b_1+c_1-1}\dots p_s^{2b_s+c_s-1}.$$ The number $x$ satisfies the condition of the problem if and only if $2b_i+c_i-1$ is divisible by $n$ and $b_i\ge a_i$, for all $i\in \{1,\dots ,s\}$. Since $n$ is odd, its multiples alternate in being even and odd, so for every $i$ we can choose a large enough $k_i\in \mathbb{N}$ such that $k_{i}n\equiv c_i-1(\mathrm{mod}2)$ and $$b_i=\frac{k_{i}n-c_i+1}{2}\ge a_i.$$

Then $2S(x)=p_1^{2b_1+c_1-1}\dots p_s^{2b_s+c_s-1}=(p_1^{k_1}\dots p_s^{k_s}{)}^n$, which shows that $x$ satisfies the condition of the problem.