HMMT February

Answer: $n$ can be 1, a prime that is $1 \bmod 3$, or the square of any prime except 3. Solution: The answer is $n$ can be 1, a prime that is $1 \bmod 3$, or the square of any prime except 3. It is easy to verify that all of these work. First note that $n$ must be $1 \bmod 3$ since 1 divides $n$ implies $f(1)$ divides $f(n)$. Next, suppose for sake of contradiction that $n=ab$, with $a>b>1$. We are given that $f(a)$ divides $f(n)$, which means $f(a)$ divides $f(n)-f(a)$. We can write this as $$a^{2}+a+1 \mid n^{2}+n-a^{2}-a=(n-a)(n+a+1)$$ Since we are working $\bmod a^{2}+a+1$, we can replace $a+1$ with $-a^{2}$, so we have $$a^{2}+a+1 \mid(n-a)\left(n-a^{2}\right)=a^{2}(b-1)(b-a)$$ However, $a^{2}+a+1$ cannot share any factors with $a$, and $0<|(b-1)(b-a)|<a^{2}+a+1$, which is a contradiction.