## Problem 2

Determine the natural numbers $n>1$ that have the property that for any divisor $d>1$ of $n$, the numbers $d^{2}+d+1$ and $d^{2}-d+1$ are prime.

Lucian Petrescu
## Solution.

Answer: $n \in\{2 ; 3 ; 6\}$.

First, we show that $n$ is square-free. If, by contradiction, there exists $d>1$ such that $d \mid n$ and $d^{2} \mid n$, then according to the hypothesis, the number $\left(d^{2}\right)^{2}+d^{2}+1=d^{4}+d^{2}+1$ would be prime. But $d^{4}+d^{2}+1=\left(d^{2}+d+1\right)(\underbrace{d^{2}-d+1}_{\geq 3})$, which is a contradiction.

Therefore, $n=p_{1} \cdot p_{2} \cdot \ldots \cdot p_{s}$, with $s \in \mathbb{N}^{*}$ and $p_{1}3\right)$ is composite, which is false. If $p \equiv 5(\bmod 6)$, then the number $p^{2}-p+1 \equiv 3(\bmod 6)\left(\right.$ and $\left.p^{2}-p+1>3\right)$ is composite, which is false.

Thus, $n$ cannot have prime factors $p \geq 5$, which implies that $p_{i} \in\{2 ; 3\}$, meaning $n \in\{2 ; 3 ; 6\}$, all three values of $n$ satisfying the hypothesis of the problem.