Balkan Mathematical Olympiad

Let $m$, $n$ and $k$ be positive integers and $p$ be a prime. Since $(n,k)=1\iff (n,n-k)=1$, we have

$$f(n)=\frac{n(n+1)}{2}-\frac{n\cdot \varphi (n)}{2},$$ where $\varphi (n)$ is the Euler function. If $m>n$, $(m,n)=1$ and $f(m)=f(n)$, then $$m(m+1-\varphi (m))=n(n+1-\varphi (n))\Rightarrow m\le n,$$ a contradiction. Therefore, if $f(n+p)=f(n)$, then $n=pk$ for some positive integer $k$ and $$(k+1)(pk+p+1-\varphi (pk+p))=k(pk+1-\varphi (pk)).$$ This implies that $$pk+1-\varphi (pk)=a(k+1)(1)$$ and $$pk+p+1-\varphi (pk+p)=ak(2)$$ for some positive integer $a$. In particular, $$(p-a)k=a-1+\varphi (pk)\Rightarrow p>a\ge 1$$ and $$a=\varphi (pk+p)-\varphi (pk)-p\equiv -1(\mathrm{mod}p-1).$$ So, we have $a=p-2$. Substituting this in (1) and (2) we obtain $$\varphi (pk)=2k+3-p(3)$$ and $$\varphi (pk+p)=2k+1+p(4)$$ We shall prove that $p\nmid k$ and $p\nmid k+1$. If $p\nmid k+1$, the relation (4) implies $p\nmid 1$, a contradiction. On the other hand if $p\nmid k$, then (3) implies $p\nmid 3$. Setting $k=3^{\alpha }{k}_1$, where $k_1$ is an integer such that $3\nmid k_1$, and substituting this in (3) we get $\varphi (k_1)=k_1$. So $k_1=1$ and $k=3^{\alpha }$. Now substituting this in (4) gives a contradiction. Using this observation, we obtain from (3) and (4) the equalities $$\varphi (k)=\frac{2(k+1)}{p-1}-1(5)$$ and $$\varphi (k+1)=\frac{2(k+1)}{p-1}+1(6)$$ In particular, $p\ge 5$ and $k+1\ge 6$. Moreover $\varphi (k+1)-\varphi (k)=2$ and either $4\nmid \varphi (k)$ or $4\nmid \varphi (k+1)$. If $4\nmid \varphi (k)$, then $k=q^{\beta }$ or $k=2q^{\beta }$, where $q$ is an odd prime and $\beta \ge 1$ is an integer. From the equality (5) we obtain $$\frac{2(k+1)}{p-1}-1=\varphi (k)\ge \frac{1}{2}\left(1-\frac{1}{q}\right)\cdot k\ge \frac{1}{2}\cdot \frac{2}{3}\cdot k=\frac{k}{3}\Rightarrow p\le 5\Rightarrow p=5.$$ If $p=5$, from (5) we obtain the relation $\varphi (k)=\frac{k-1}{2}$. So, $k$ must be odd, $k+1$ must be even and $\varphi (k+1)\le \frac{k+1}{2}$. This contradicts the equality (6). If $4\nmid \varphi (k+1)$, then $k+1=q^{\beta }$ or $k+1=2q^{\beta }$, where $q$ is an odd prime and $\beta \ge 1$ is an integer. From the equality (6) we obtain $$\frac{2(k+1)}{p-1}+1=\varphi (k+1)\ge \frac{k+1}{3}.$$ If $p>7$, then this implies $$\frac{6}{p-7}\ge \frac{2(k+1)}{p-1}$$ and therefore by (5) we must have $$\varphi (k)\le \frac{13-p}{p-7}$$ Which is impossible. On the other hand, if $p\le 7$, then $p=7$ and, as $\frac{p-1}{2}$ divides $k+1$, we also have $q=3$. Using (6) again, we see that $k+1=2\cdot 3^{\alpha }$ leads to a contradiction, and $k+1=3^{\alpha }$ leads to $k+1=3$, which was already ruled out.