A polynomial divisible by primes of special form

Question

$\textbf{Problem:}$Let $p$ be a prime number of the form $9k + 1$. Show that there exists an integer n such that $p | n^3 - 3n + 1$.

$\textbf{Source:}$Here

My only idea was that $n^3-3n+1$ might form a complete residue modulo such primes. So, I tried it out for $19$ and it turned out to be wrong. After that I could not find anything useful so I read the solution. But I don't understand it. Any elaboration on the solution given in the provided link or any new solution both are appreciated. Thanks in advance

Answer 1

Hint: $ x^3 - 3x + 1 $ is the minimal polynomial of $ \zeta_9 + \zeta_9^{-1} $ over $ \mathbf Q $, and if $ p \equiv 1 \pmod{9} $ then there is an element of order $ 9 $ in $ (\mathbf Z/p \mathbf Z)^{\times} $.

Answer 2

Elementary solution:

Suppose $n=t-1$, putting in we get:

$A=n^3-3n+1=t^3-3t^2+3$

For $t=3m$ we get:

$A=27m^3-27+3=3[9(m^3-m^2)+1]$

We can assume $m^3-m^2=k$ so $9k+1|A$

Then $n=3m-1$

For example:

$m=2$, $\rightarrow:$, $p=37$, $n=5$

$m=3$, $\rightarrow:$, $p=163$, $n=8$

$m=4$, $\rightarrow:$, $p=433$, $n=11$

Hence values of n make an arithmetic progression .