45th Mongolian Mathematical Olympiad

If for $k$, $1\le k<n$ and $(k,m)=1$ then $(m-k,n)=1$. Hence, the positive integers less than or equal to $m$ can be divided into such pairs $(k,m-k)$, which pairs number is $\frac{\phi (m)}{2}$. Thus, we should find $m$ such that $n\mid \frac{\phi (m)}{2}$.

Now, we will show that for $n\ge 2$, $n\mid \frac{\phi (n^2)}{2}$, ($\frac{\phi (n^2)}{2}$ is divisible by $2$).

We can write $n$ as follows: $n=2^k{p}_1^{k_1}\dots p_s^{k_s}$.

a). $k=0$, in other words, $k$ is odd. Hence, we have $$\frac{\phi (n^2)}{2}=p_1^{2k_1-1}\dots p_s^{2k_s-1}\cdot \frac{(p_1-1)\dots (p_s-1)}{2}$$ and for every $i:2k_i-1\ge k_i$, hence $n\mid \frac{\phi (n^2)}{2}$.

b). Let $k\ge 1$, we get $\frac{\phi (n^2)}{2}=2^{2k-2}{p}_1^{2k_1-1}\dots p_s^{2k_s-1}(p_1-1)\dots (p_s-1)$, for arbitrary $i:2k_i-1$ and $\frac{\phi (n^2)}{2}$ is divisible by $2^{2k-2}{p}_1^{2k_1-1}\dots p_s^{2k_s-1}$

because $p_i-1$ is even. Therefore, if $2k-2+s\ge k$ then $\frac{\phi (n^2)}{2}$ is divisible by $n$. Above inequality not only holds for $k+s=1$, but $k\ge 1$ and $n>2$, hence $k+s>1$.