# why does $P(X) = X^3+X+1$ have at most 1 root in $F_p$?

why does $$P(X) = X^3+X+1$$ has at most 1 root in $$F_p$$ ?

I could fact check this on Sage for small values of $$p$$.

For example $$p=5$$ or $$7$$ or $$19$$; there is no root.

If $$p = 11, 2$$ is the only root.

If $$p = 13, 7$$ is the only root.

If $$p = 17, 11$$ is the only root.

I also realize that there can't be only 2 roots a1 and a2 because a3 = -(a1+a2) will be a root as well.

• Given any monic integer polynomial $f$, there will be infinitely many primes for which $f$ splits into linear factors over $\Bbb F_p$. – Angina Seng Jun 1 at 14:32

It's not true.

$$3$$ and $$14$$ are roots in $$F_{31}$$.

• sorry for the stupid question. Should I delete this question ? – Fagui Curtain Jun 1 at 14:29
• I don't think it was a stupid question – J. W. Tanner Jun 1 at 14:30
• NB you also showed that 2 roots only is possible, contrarily to what i thought. – Fagui Curtain Jun 1 at 14:43
• @Fagui Curtain That's true, but note that the root $X = 14$ has multiplicity $2$, so that $P$ splits into a product of linear factors modulo $31$. Comparing degrees shows that a cubic polynomial cannot have exactly two roots. on the other hand, if $F(X) \in \Bbb Z[X]$ does not have a double root then $F(X)$ only has a multiple root for finitely many modulo $p$, namely the prime factors of the discriminant $\Delta_F$. Computing gives $F_P = -31$, so $31$ is the only prime $p$ for which $P$ has exactly $2$ distinct roots. – Travis Willse Jun 1 at 15:19
• thanks very much for this reminder ! – Fagui Curtain Jun 1 at 16:32

The primes other for which $$x^3 + x + 1$$ has three distinct roots are all those that can be represented by $$x^2 + xy + 8 y^2$$ other than 31 itself

 31,     47,     67,    131,    149,    173,    227,    283,    293,    349,
379,    431,    521,    577,    607,    617,    653,    811,    839,    853,
857,    919,    937,    971,   1031,   1063,   1117,   1187,   1213,


The primes for which $$x^3 + x + 1$$ has no roots are all those that can be represented by $$2x^2 + xy + 4 y^2$$ other than 31 itself

  2,      5,      7,     19,     41,     59,     71,     97,    101,    103,
107,    109,    113,    157,    163,    191,    193,    211,    233,    257,
281,    307,    311,    317,    359,    373,    397,    419,    421,    439,
443,    467,    479,    503,    541,    547,    563,    593,    599,    659,
661,    683,    691,    701,    727,    733,    751,    769,    877,    887,
907,    977,    997,


The primes for which the cubic has one root are all odd primes $$p$$ such that Legendre symbol $$(-31|p) = -1$$ Note that $$31 \equiv 3 \pmod 4,$$ so for any odd prime other than $$31$$ itself, $$(-31|p) = (p|31)$$

• I asked an innocent question, and i find out that many people ask themselves these kind of questions, and more importantly find answers and meaning to it !! – Fagui Curtain Jun 1 at 14:51

The first prime for which $$x^3+x+1$$ has $$3$$ distinct roots is $$47$$, where the roots are $$24$$, $$34$$ and $$35$$. Hmm... it looks like the primes for which $$x^3+x+1$$ splits are OEIS sequence A033221, the primes of the form $$x^2 + 31 y^2$$.

Meanwhile, the numbers that can not be expressed with integers as $$2x^2 + xy + 4 y^2 - z^3 - z$$ are $$\pm C_n,$$ where the sequence of $$C_n$$ begins $$1, 869, 25171, 21118439, 611705641, 513220303709, 14865670462411,$$ and obeys $$C_{n+4} = 24302 C_{n+2} - C_n.$$ Put another way, the numbers $$27 C_n^2 + 4$$ are of the form $$31 D_n^2$$