# A polynomial divisible by primes of special form

$$\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

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}$$.

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 .

• How do you "assume $m^3 - m^2 = k$"? E.g. if $k=2$, then $9k+1 = 19$ is prime. What is your corresponding $m$ or $n$? – Calvin Lin Jan 18 at 6:48
• @CalvinLin, see edit. – sirous Jan 18 at 7:05
• As I asked, for prime $p = 19$, what's the corresponding $m$ or $n$? You have shown that it is true for some primes of the form $p = 9k+1$, not for all primes of the form. – Calvin Lin Jan 18 at 17:08