Let $f(n)=n^3-3n+1$. It can be proved that for any prime $p$ and integer $n$ such that $p\mid f(n)$ we have either $p=3$ or $p\equiv\pm1\pmod 9$ (see below).

Indeed, suppose that for prime number $p$ and integer $n$ we have $p\mid n^3-3n+1$. Firstly, note that if $x=t+\frac{1}{t}$, then $$ f(x)=t^3+\frac{1}{t^3}+1=\frac{t^6+t^3+1}{t^3}. $$

Now we will consider two cases:

Case 1. In $\mathbb{F}_p\backslash\{0\}$ there is a $a$ such that $n\equiv a+\frac{1}{a}\pmod p$. Then, we have $$ a^6+a^3+1\equiv 0\pmod p, $$ so $a^9\equiv 1\pmod p$. Moreover, $x^{p-1}\equiv 1\pmod p$. Thus, the order $d$ of $a$ in $\mathbb{F}_p^{\times}$ must divide $\gcd(p-1,9)$. If $d\in\{1,3\}$, then $a^3\equiv 1\pmod p$, so $p=3$. Otherwise, $d=9$ and $9\mid p-1$, as desired.

Case 2. There is no $a\in\mathbb{F}_p$ such that $n\equiv a+\frac{1}{a}$. Then, we can consider the extension $\mathbb{F}_p(a)$, where $a$ is a root of the polynomial $x^2-nx+1=0$ (which is irreducible in $\mathbb{F}_p$ due to our assumption). Note that $|\mathbb{F}_p(a)|=p^2$ since the degree of this extension is 2. Similarly, as in the first case we deduce that in $\mathbb{F}_p(a)$ $$ a^6+a^3+1=0,~\text{so}~a^9=1. $$ If $d$ is the order of $a$ in $\mathbb{F}_p(a)^{\times}$, then $d\mid\gcd(p^2-1,9)$. As in the first case, if $d\in\{1,3\}$, then $a^3=1$ in $\mathbb{F}_p(a)$ and $p=3$. Otherwise, $d=9$, so $9\mid p^2-1$. Therefore, $p\equiv\pm 1\pmod 9$, as desired.

I am interested in elementary proof of this fact (without using field extensions, groups, etc.). Is this possible?


A "problem" with a fully elementary proof is that concepts are often pulled out of nowhere. This is already seen in your proof, since you do not explain why you consider writing $n \equiv a + 1/a \bmod p$. How did you decide to try to solve such a congruence? Why are you interested in a proof making no use of groups or fields?

Motivation for the congruence $n \equiv a + 1/a \bmod p$ comes from looking in $\mathbf R$. The polynomial $x^3 - 3x + 1$ has three real roots: $2\cos(2\pi/9)$, $2\cos(4\pi/9)$, and $2\cos(8\pi/9)$. In terms of the primitive 9th root of unity $z = e^{2\pi i/9}$, there are 6 primitive 9th roots of unity $z$, $z^2$, $z^4$, $z^5 = 1/z^4$, $z^7 = 1/z^2$, and $z^8 = 1/z$, and the three roots of $x^3 - 3x + 1$ are the sum of a primitive 9th root of unity and its complex conjugate: $2\cos(2\pi/9) = z + \overline{z} = z + 1/z$, $2\cos(4\pi/9) = z^2 + \overline{z^2} = z^2 + 1/z^2$, and $2\cos(8\pi/9) = z^4 + \overline{z^4} = z^4 + 1/z^4$. This suggests that when $x^3 - 3x + 1$ has a root $n \bmod p$, $n \bmod p$ should have the form $a + 1/a$ for a 9th root of unity $a$ in characteristic $p$. That is analogous to $2\cos(2\pi/9) = z + 1/z$ above. The intuition behind $a^6 + a^3 + 1 \equiv 0 \bmod p$ comes from $a \bmod p$ being a primitive 9th root of unity in characteristic $p$ and $x^9 - 1$ factoring like this: $$ x^9 - 1 = (x-1)(x^2+x+1)(x^6 + x^3 + 1). $$ In this factorization, the root of $x - 1$ is $1$ and the roots of $x^2+x+1$ are the nontrivial cube roots of unity, so the roots of $x^6 + x^3 + 1$ are the primitive 9th roots of unity.

The condition $p \equiv \pm 1 \bmod 9$ that you are interested in is the same as $p^2 \equiv 1 \bmod 9$, and that very strongly suggests looking at the field $\mathbf F_{p^2}$ and showing its group of nonzero elements contains an element of order $9$ (primitive 9th root of unity in characteristic $p$). Then $9 \mid (p^2-1)$ by Lagrange's theorem. But you want to avoid group theory. I don't see how to derive $p^2 \equiv 1 \bmod 9$ in a nice way by working only in $\mathbf F_p^\times$ instead of in $\mathbf F_{p^2}^\times$.

If $r$ is one of the roots of $x^3-3x+1$ in $\mathbf R$ then the other two roots are $r^2-2$ and $-r^2-r+2$. This has an analogue in $\mathbf F_p$ if $p \not= 3$ and $n^3 - 3n + 1 \equiv 0 \bmod p$ for an integer $n$: $x^3 - 3x + 1$ has three different roots in $\mathbf F_p$, namely $n \bmod p$, $n^2 - 2 \bmod p$, and $-n^2 - n + 2 \bmod p$. (When $p = 3$ these roots are all equal.) Maybe you can get something useful by working with all three of the roots in $\mathbf F_p$ and not just one of the roots mod $p$.

[Update: since you know some field theory already, here is how I would solve this problem using field theory, rather than the method using more machinery below. The key insight, as mentioned above, is that $x^3 - 3x + 1$ has roots of the form $z + 1/z$ as $z$ runs over primitive 9th roots of unity. This is true in $\mathbf C$ and in fact it's true in every field where there are 9 ninth roots of unity: if $z^9 = 1$ and $z^3 \not= 1$ then $z + 1/z$ is a root of $x^3 -3x + 1$. For a prime $p \not= 3$, the polynomial $x^9 - 1$ has nine distinct roots in characteristic $p$ and only 3 of those roots are cube roots of unity, so $x^9-1$ has 6 roots in characteristic $p$ that are primitive 9th roots of unity. Pairing the 6 roots together as $z$ and $1/z$, the three sums $z + 1/z$ are the three roots of $x^3 - 3x + 1$. All 3 roots can be expressed in terms of any one root $r$: the roots are $r$, $r^2 - 2$, and $-r^2 - r + 2$, so a field containing one root of $x^3 - 3x + 1$ contains all three of its roots. Let $\zeta$ be a primitive 9th root of unity in characteristic $p$. It does not have to lie in $\mathbf F_p$, but $\mathbf F_p(\zeta)$ is a finite field since $\zeta$ is a root of $x^6 + x^3 + 1$. Since $\zeta + 1/\zeta$ is a root of $x^3 - 3x + 1$ and a field containing one root of this polynomial contains all three roots, your question is about showing, for $p \not= 3$, that $\zeta + 1/\zeta$ lies in $\mathbf F_p$ if and only if $p \equiv \pm 1 \bmod 9$.

("If") In a field $K$ of characteristic $p$, the elements of its subfield $\mathbf F_p$ are the solutions in $K$ to $a^p = a$: that polynomial equation has at most $p$ solutions in $K$ and all $p$ elements of $\mathbf F_p$ are solutions of that equation (the $p-1$ nonzero elements of $\mathbf F_p$ satisfy $a^{p-1} = 1$, so $a^p = a$, and $a = 0$ also fits $a^p = a$). If $p \equiv \pm 1 \bmod 9$ then $\zeta + 1/\zeta \in \mathbf F_p$ since $\zeta + 1/\zeta$ equals its own $p$th power: $$ (\zeta + 1/\zeta)^p = \zeta^p + (1/\zeta)^p = \zeta^p + 1/\zeta^p = \zeta + 1/\zeta $$ since $\zeta^p$ only depends on $p \bmod 9$ and thus $\zeta^p$ is $\zeta$ or $1/\zeta$ from $p \equiv \pm 1 \bmod 9$.

("Only if") The field extension $\mathbf F_p(\zeta)/\mathbf F_p(\zeta + 1/\zeta)$ has degree at most $2$ since $\zeta$ is a root of $x^2 - (\zeta + 1/\zeta)x + 1$. If $\zeta + 1/\zeta$ lies in $\mathbf F_p$, then $\mathbf F_p(\zeta)/\mathbf F_p$ has degree at most 2, so $\zeta \in \mathbf F_{p^2}$ (there is exactly one quadratic extension field of $\mathbf F_p$ and it has size $p^2$). That implies $\zeta^{p^2-1} = 1$, since $\mathbf F_{p^2}^\times$ is a multiplicative group of order $p^2-1$. Since $\zeta$ has multiplicative order 9 (it is a primitive 9th root of unity!), from $\zeta^{p^2-1} = 1$ we must have $9 \mid (p^2-1)$, so $p^2 \equiv 1 \bmod 9$ and thus $p \equiv \pm 1 \bmod 9$.

This concludes my update to this answer.]

I do not see a fully elementary proof for what you seek, but I do see a natural proof if the reader knows algebraic number theory. First of all, the motivation for knowing that all the roots of $x^3-3x+1$ are expressible in terms of one of them comes from Galois theory since $x^3 - 3x+1$ is irreducible over $\mathbf Q$ with a square discriminant $81$. That the discriminant is $81$ tells us by algebraic number theory that the only ramifying prime in $\mathbf Q(r)$ is 3. The Kronecker-Weber theorem tells us the abelian Galois extension $\mathbf Q(r)/\mathbf Q$ has to lie in some cyclotomic field, and we are led to check how $\mathbf Q(r)$ is related to the 9th cyclotomic field because the only primes at which the $m$th cyclotomic field ramifies are factors of $m$. So $\mathbf Q(r)$ should lie in a 3-power cyclotomic field. In fact, $\mathbf Q(r)$ is the real subfield of $\mathbf Q(\zeta_9)$, where $\zeta_9 = e^{2\pi i/9}$. The connection between prime splitting in Galois extensions of $\mathbf Q$ and Frobenius elements in Galois groups over $\mathbf Q$ tells us $p$ splits in $\mathbf Q(r)$ if and only if $p \equiv \pm 1 \bmod 9$ because under the natural isomorphism of ${\rm Gal}(\mathbf Q(\zeta_9)/\mathbf Q)$ with $(\mathbf Z/9\mathbf Z)^\times$, the real subfield $\mathbf Q(r) = \mathbf Q(\zeta_9 + 1/\zeta_9)$ corresponds to the subgroup $\pm 1 \bmod 9$. This, to me, explains why $x^3 - 3x + 1$ has a root mod $p$ if and only if $p=3$ or $p \equiv \pm 1 \bmod 9$ in a very conceptual way. Of course it does not at all qualify as an "elementary proof" making no use of abstract algebra. Sorry.

  • $\begingroup$ Actually, I am familiar only with basic notions of the field theory (like finite extensions, but not Galois theory). I came up with this proof because I recalled that polynomial $t^3-3t$ arises when one needs to compute $a^n+a^{-n}$ using $b=a+a^{-1}$, so for me this was like a miracle. (But connection becomes more clear if we note that for $a=e^{i\alpha}$ we have $a^n+a^{-n}=2\cos n\alpha$.) Of course, it's useful to understand the "nature" of this, so thank you for that. $\endgroup$ – richrow Aug 23 '20 at 19:04
  • $\begingroup$ The polynomials $f_n(t)$ for which $x^n + x^{-n} = f_n(x + 1/x)$ are the Chebyshev polynomials (up to a scaling renormalization by a power of $2$), so $f_2(t) = t^2 - 2$ and $f_3(t) = t^3 - 3t$. That $f_3(t)$ has terms similar to the nonconstant terms in $x^3 - 3x + 1$ is, I think, an instance of the "strong law of small numbers" (i.e., a coincidence). You are not going to find $t^3 - 3t - 3$ has properties like that of $t^3 - 3t + 1$, for example. $\endgroup$ – KCd Aug 24 '20 at 18:21
  • $\begingroup$ Yes, it was a coincidence. Considering $f(x+x^{-1})$ works because we obtain $\frac{x^6+x^3+1}{x^3}$ or $\Phi_9(x)/x^3$ (and it is known that for prime $p\mid\Phi_n(a)$ we have $p\mid n$ or $p\equiv 1\pmod n$). As far as I understand we obtain cyclotomic polynomial because roots of $f$ are $2\cos 2\pi k/9$, where $\gcd(k,9)=1$. By the way, I think that we can construct a polynomial $g_n(x)$ with similar properties, i. e. if $p\mid g_n(a)$, then $p\mid n$ or $p^2\equiv 1\pmod n$. $\endgroup$ – richrow Aug 25 '20 at 7:35
  • $\begingroup$ Actually, yes, we just to need to choose $g_n$ such that $g_n(x+x{-1})=\Phi_n(x)/x^{\varphi(n)/2}$ or simply $g_n(x)=\prod\limits_{(k,n)=1, 0<k<n/2}(x-2\cos 2\pi k/n)$. $\endgroup$ – richrow Aug 25 '20 at 7:36

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.