Team selection tests for BMO 2018

First assume $n$ is a prime number. Thus $\phi (n)=n-1\mid n^2+3=(n-1)(n+1)+4$, implying $n-1\mid 4$. We deduce that $n=2,3$ or $5$.

From now on, assume $n$ is composite and set $n={\prod }_{i=1}^k{p}_i^{{\alpha }_i}$, where $k$ is the number of distinct prime divisors of $n$. Since $n\ge 3$, $\phi (n)$ is even. In particular, the condition $\phi (n)\mid n^2+3$ shows that $n$ is odd and so the $p_i$'s are all odd. It follows that $$2^k\mid \phi (n)=\prod _{i=1}^k{p}_i^{{\alpha }_i-1}(p_i-1).$$ So $n^2+3$ is divisible by $2^k$ implying that $k\le 2$. Moreover, if ${\alpha }_i\ge 2$ then $p_i\mid \phi (n)$, so $p_i\mid n^2+3$, forcing $p_i=3$. In this case, $9\nmid n^2+3$ and $9\nmid \phi (n)$. This shows that ${\alpha }_i=2$. Our discussion shows that if the composite $n\ge 3$ satisfies the problem then $n=3^2=9$ or $n=9p$, or $n=pq$ for some odd primes $p,q$. Of course, $n=9$ is a solution of our problem.

- Suppose $n=9p$. Then $\phi (n)=6(p-1)$ and $n^2+3=81(p-1)(p+1)+84$. Therefore, $3(p-1)\mid 84$, or equivalently $p-1\mid 28$. It follows that $p=5$ or $p=29$. But in both cases, we have $8\mid \phi (n)$, contradiction.

- Suppose $n=pq$, where $p,q$ are odd primes. First, consider the case $q=3$ (the case $p=3$ is of course similar). Then $\phi (n)=2(p-1)$ so $n^2+3=9(p-1)(p+1)+12$. It follows that $2(p-1)\mid 12$, and $p-1\mid 6$, implying $p=3$ or $p=7$. In this case we obtain a new solution $n=pq=3\times 7=21$ of our problem.

Now, suppose $p,q>3$. Thus, $3\nmid n^2+3$ so $3\nmid (p-1)(q-1)$. This shows that $p,q\equiv 2(\mathrm{mod}3)$. Since $(p-1)(q-1)\mid p^2{q}^2+3=(p^2-1)(q^2-1)+p^2+q^2+2$ so $(p-1)(q-1)\mid p^2+q^2+2$. Set $$p^2+q^2+2=k(p-1)(q-1),$$ where $k$ is a positive integer. Set $p=2x+1$, $q=2y+1$, then the above equation reads $x^2+y^2+x+y+1=kxy$, or equivalently, $$x^2-(ky-1)x+y^2+y+1=0.$$ By a Vieta jumping technique, we deduce that $k=5$. Thus, we have $$5(p-1)(q-1)=p^2+q^2+2.$$ But then $p\equiv q\equiv 2(\mathrm{mod}3)$ and the left hand side is $\equiv 2(\mathrm{mod}3)$, while the right hand side is $\equiv 1(\mathrm{mod}3)$, contradiction.

Therefore, all numbers satisfy the given condition are $n\in \{1,2,3,5,9,21\}$.