# If a prime natural number $p\neq 3$ divides $a^3-3a+1$ for some integer $a$, then $p\equiv \pm1\pmod{9}$.

$$\textbf{Problem:}$$ Let $$a$$ be a positive integer and $$p$$ a prime divisor of $$a^3-3a+1$$, with $$p \neq 3$$. Prove that $$p$$ is of the form $$9k+1$$ or $$9k-1$$, where $$k$$ is an integer.

I tried to complete the cube which didn't turn out to be anything good. If the condition asked for $$p$$ to be only of the form $$9k+1$$, I would try to show that $$a$$ has order $$9 \pmod{p}$$. But the given condition seems somewhat odd to me. So, overall I could hardly make any real progress.

Any kind of hint or solutions are appreciated.

• Similar theme elsewhere 1, 2, 3. At least one of them out of a contest. I wonder what is the high school level argument? – Jyrki Lahtonen Sep 4 '20 at 19:30
• @JyrkiLahtonen Actually, I asked about such an argument here math.stackexchange.com/questions/3800911/…. It seems that there is no elementary proof for this (partly because of condition $9\mid p^2-1$ which is connected to finite fields of order $p^2$). – richrow Sep 4 '20 at 19:57
• Thanks for the link @richrow. Sorry I missed it earlier. – Jyrki Lahtonen Sep 4 '20 at 20:30

## 2 Answers

Let $$f(x)=x^3-3x+1$$. Then, $$g(t):=t^3\,f\left(t+\frac1t\right)=t^3\,\left(\left(t+\frac1t\right)^3-3\left(t+\frac1t\right)+1\right)\,.$$ Hence, $$g(t)=t^6+t^3+1=\Phi_9(t)\,,$$ where $$\Phi_n$$ is the $$n$$-th cyclotomic polynomial for each positive integer $$n$$.

Let $$p\neq 3$$ be a prime natural number. We work in $$\mathbb{F}_p$$. Suppose that $$f(a)=0$$ for some $$a\in\mathbb{F}_p$$. We consider the equation $$t+\frac{1}{t}=a\,.\tag{*}$$ Suppose that this equation has a solution $$t=b$$ for some $$t\in\mathbb{F}_p\setminus\{0\}$$, then $$\Phi_9(b)=0$$. As $$t^9-1$$ is divisible by $$\Phi_9(t)$$, we conclude that $$b^9-1=0\,.$$ However, $$b^{p-1}-1=0$$ as well. Consequently, if $$d=\gcd(9,p-1)$$, then $$b^{d}-1=0\,.$$ It is easily seen that $$d\neq 1$$ and $$d\neq 3$$; otherwise $$b^3=1$$, whence $$0=\Phi_9(b)=b^6+b^3+1=(b^3)^2+(b^3)+1=1^2+1+1=3\,,$$ contradicting the assumption that $$p\neq 3$$. Thus, $$d=9$$ implying that $$9\mid p-1$$.

Suppose now that (*) has a solution $$t=b$$, where $$b\in\mathbb{F}_{p^2}\setminus\mathbb{F}_p$$. Since $$\Phi_9(b)=0$$, we conclude as before that $$b^9-1=0\,.$$ However, since $$b\in\mathbb{F}_{p^2}\setminus\{0\}$$, we have $$b^{p^2-1}-1=0\,.$$ Therefore, $$b^{d}-1=0\,,$$ where $$d:=\gcd(9,p^2-1)$$. Using the same argument as the previous paragraph, $$d=1$$ and $$d=3$$ are ruled out. Therefore, $$d=9$$, making $$9\mid p^2-1=(p-1)(p+1)$$. Since $$3$$ divides exactly one of the numbers $$p-1$$ and $$p+1$$, we conclude that $$9\mid p-1$$ or $$9\mid p+1$$, establishing the claim.

Conversely, let $$p$$ be a prime natural number such that $$p\equiv \pm1 \pmod{9}$$. Then, $$9\mid p^2-1$$. Therefore, $$\Phi_9(t)$$ is a factor of $$t^{p^2-1}-1$$. Thus, $$\Phi_9(t)$$ splits into linear factors in $$\mathbb{F}_{p^2}$$. Let $$b_1,b_2,b_3,b_1^{-1},b_2^{-1},b_3^{-1}$$ be the six roots of $$\Phi_9(t)$$ in $$\mathbb{F}_{p^2}\setminus\{0\}$$. Then, the polynomial $$f(x)=x^3-3x+1\in\mathbb{F}_p[x]$$ has three roots $$b_1+b_1^{-1}$$, $$b_2+b_2^{-1}$$, and $$b_3+b_3^{-1}$$ in $$\mathbb{F}_{p^2}$$. Consequently, $$f(x)$$ cannot be irreducible over $$\mathbb{F}_p$$. Ergo, $$f(x)$$ has a root $$a\in\mathbb{F}_p$$. Therefore, we have the following proposition.

Proposition. Let $$p\neq 3$$ be a prime natural number. There exists an integer $$a$$ such that $$a^3-3a+1$$ is divisible by $$p$$ if and only if $$p\equiv \pm1\pmod{9}$$, or equivalently, $$p\equiv \pm1\pmod{18}$$.

Remark. In the case where $$p\equiv \pm1\pmod{9}$$, it can be easily seen that $$f(x)$$ has exactly three distinct roots in $$\mathbb{F}_p$$. This is because the discriminant of $$f(x)$$ is $$81\not\equiv 0\pmod{p}$$, and the roots of $$f(x)$$ are of the form $$a$$, $$h(a)$$, and $$h\big(h(a)\big)$$ for some $$a\in\mathbb{F}_p$$, where $$h(x):=x^2-2$$. See this related question: Expressing the roots of a cubic as polynomials in one root.

Without all details: If $$\zeta$$ is a primitive $$9$$th root of unity then $$x^3-3x+1$$ is the minimal polynomial of $$\alpha = \zeta + \zeta^{-1}$$. So if $$x^3-3x+1$$ has a root $$\beta \pmod p$$ for some prime then $$\mathbb F_{p^2}$$ has a root of $$x^2-\beta x+1$$ and if $$p \neq 3$$ then that root is a primitive $$9$$th root of unity. That implies that $$9 \mid p^2-1$$ since $$\lvert \mathbb F_{p^2}^{\ast} \rvert = p^2-1$$.

• I would really like some details.If you get some free time please consider adding some details. – Yes it's me Sep 4 '20 at 18:59