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

  • $\begingroup$ Similar theme elsewhere 1, 2, 3. At least one of them out of a contest. I wonder what is the high school level argument? $\endgroup$ – Jyrki Lahtonen Sep 4 '20 at 19:30
  • 3
    $\begingroup$ @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$). $\endgroup$ – richrow Sep 4 '20 at 19:57
  • $\begingroup$ Thanks for the link @richrow. Sorry I missed it earlier. $\endgroup$ – Jyrki Lahtonen Sep 4 '20 at 20:30

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.