As $9\mid P-1$, $9\mid P^2-1$ so we may take the an element $t$ of $\mathbb{F}_{P^2}$ with order 9. Then, note that $t+\frac1t\in\mathbb{F}_P$ and $\left(t+\frac1t\right)^3-3\left(t+\frac1t\right)+1=t^3+\frac1{t^3}+1=\frac{t^6+t^3+1}{t^3}=0$, so we may take $n\equiv t+\frac1t\pmod{P}$.

Sorry, but how does one know that $\mathbb{F}_{P^2}$ has an element with order $9$?

Because it's well known that the group $(\mathbb{F}_{p^2}, \times)$ is cyclic. Btw, this problem is a weaker version of Brazil 2017 P6

What is $\mathbb{F} _{p^2}$ ? I don't know how to search about it.

It is a field with $p^2$ elements.

If you are more familiar with elementary number-theoretic language; then, take $p=18k+1$, and, let, $g$ be the primitive root, modulo $p$. Clearly, $$ g^{9k}+1 \equiv 0 \pmod{p}\implies (g^{3k}+1)(g^{6k}-g^{3k}+1) \equiv 0 \pmod{p}. $$Clearly, $p\nmid g^{3k}+1$ (otherwise, we would have, $p\mid g^{6k}-1$, a contradiction). Hence, $p\mid g^{6k}+g^{3k}+1$. Now, suppose, we pick $n=a+b$; for some $a,b$, to be determined later. Observe that, $$ n^3-3n+1 = a^3+b^3 +3ab(a+b)-3(a+b)+1. $$Hence, it seems wise to pick, $ab\equiv 1 \pmod{p}$. With this, the problem boils down to finding an $a$, such that, $$ a^3+a^{-3}+1 \equiv 0 \pmod{p}. $$We have already found that, $g^{6k}-g^{3k}+1\equiv 0 \pmod{p}$; but note that, combining this, with, $g^{9k}\equiv -1\pmod{p}$; we have, $g^{6k}+g^{-6k}+1\equiv 0 \pmod{p}$. Hence, select, $a=g^{2k}$; and, $n=g^{2k}+g^{-2k}$, and done.

grupyorum wrote: If you are more familiar with elementary number-theoretic language; then, take $p=18k+1$, and, let, $g$ be the primitive root, modulo $p$. Clearly, $$ g^{9k}+1 \equiv 0 \pmod{p}\implies (g^{3k}+1)(g^{6k}-g^{3k}+1) \equiv 0 \pmod{p}. $$Clearly, $p\nmid g^{3k}+1$ (otherwise, we would have, $p\mid g^{6k}-1$, a contradiction). Hence, $p\mid g^{6k}+g^{3k}+1$. Now, suppose, we pick $n=a+b$; for some $a,b$, to be determined later. Observe that, $$ n^3-3n+1 = a^3+b^3 +3ab(a+b)-3(a+b)+1. $$Hence, it seems wise to pick, $ab\equiv 1 \pmod{p}$. With this, the problem boils down to finding an $a$, such that, $$ a^3+a^{-3}+1 \equiv 0 \pmod{p}. $$We have already found that, $g^{6k}-g^{3k}+1\equiv 0 \pmod{p}$; but note that, combining this, with, $g^{9k}\equiv -1\pmod{p}$; we have, $g^{6k}+g^{-6k}+1\equiv 0 \pmod{p}$. Hence, select, $a=g^{2k}$; and, $n=g^{2k}+g^{-2k}$, and done. Thanks, nice solution !

ABCDE wrote: As $9\mid P-1$, $9\mid P^2-1$ so we may take the an element $t$ of $\mathbb{F}_{P^2}$ with order 9. Then, note that $t+\frac1t\in\mathbb{F}_P$ and $\left(t+\frac1t\right)^3-3\left(t+\frac1t\right)+1=t^3+\frac1{t^3}+1=\frac{t^6+t^3+1}{t^3}=0$, so we may take $n\equiv t+\frac1t\pmod{P}$. Why is $t+\frac1t\in\mathbb{F}_P$ ?

@above Let $g$ be the primitive root of $\mathbb{F}_{P^2}$. And let $t=g^{(p^{2}-1)/7}$. Then we can know that $t^{p+1}=1$ so $(t+\frac1t)^p=t+\frac1t$. Hence $t+\frac1t\in\mathbb{F}_P$ .