Find all primes $p$ such that $x^3+x+1\equiv0\pmod p$ has $3$ incongruent solutions.

Question

Find all primes $p$ such that $$x^3+x+1\equiv0\pmod p$$ has $3$ incongruent solutions.

By a standard result in number theory, it has $3$ incongruent solutions iff there exists $q(x),r(x)\in\mathbb{Z}[x]$ with $\deg r(x)<3$ such that $$x^p-x=(x^3+x+1)\,q(x)+p\cdot r(x).$$ I am unable to proceed from here. I tried to write out the coefficients of $q(x)$ and multiply out, but it was in vain. How do I solve this problem? Thanks in advance!

I am unclear about what tags to add, so please fix this.

Answer 1

Such questions lead rapidly to problems in algebraic number theory. Here we need to know at which primes the number field generated by a zero of $x^3+x+1$ splits completely. As this number field does not have an Abelian Galois group, the set of such primes cannot be described simply in terms of congruence conditions.

The discriminant of $f(x)=x^3+x+1$ is $-31$. This means that the splitting field of $f$ is the Hilbert class field of $\mathbb{Q}(\sqrt{-31})$. The primes $p$ that split completely in this field, that is those for which $f(x)\equiv0$ (mod $p$) has three solutions, are those represented by the quadratic form $a^2+ab+8b^2$ (the principal binary quadratic form of discriminant $-31$).

For proofs and much more discussion see David Cox's book Primes of the Form $x^2+ny^2$.

PDF of the entire article, page shown below

Answer 2

CW answer. To fill in Shark's answer, these are the primes up to 2100 that you want. Well, almost. Most people do not call $1$ a prime, but it is my computer program. Also things "ramify" at $31,$ there is a double root, which they don't want. A Thought: maybe this came up because $2017$ is one of these primes, and this is year $2017.$ Still not a reasonable question for any contest anywhere.

GP-PARI:

parisize = 4000000, primelimit = 500509
? factormod( x^3 + x + 1, 31)
%1 = 
[Mod(1, 31)*x + Mod(17, 31) 2]

[Mod(1, 31)*x + Mod(28, 31) 1]

? factormod( x^3 + x + 1, 47)
%2 = 
[Mod(1, 47)*x + Mod(12, 47) 1]

[Mod(1, 47)*x + Mod(13, 47) 1]

[Mod(1, 47)*x + Mod(22, 47) 1]

? factormod( x^3 + x + 1, 67)
%3 = 
[Mod(1, 67)*x + Mod(4, 67) 1]

[Mod(1, 67)*x + Mod(9, 67) 1]

[Mod(1, 67)*x + Mod(54, 67) 1]

=======================================================

? factormod( x^3 + x + 1, 2017)
%4 = 
[Mod(1, 2017)*x + Mod(176, 2017) 1]

[Mod(1, 2017)*x + Mod(267, 2017) 1]

[Mod(1, 2017)*x + Mod(1574, 2017) 1]

? 

=======================================================

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./primego
Input three coefficients a b c for positive f(x,y)= a x^2 + b x y + c y^2 
1 1 8
Discriminant  -31

Modulus for arithmetic progressions? 
31
Maximum number represented? 
2100

      1,     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,
   1237,   1259,   1303,   1327,   1451,   1493,   1523,   1559,   1583,   1619,
   1663,   1721,   1723,   1741,   1879,   1931,   1973,   1993,   2003,   2017,


    0    1    2    4    5    7    8    9   10   14   16   18   19   20   25   28

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ date
Fri Apr 14 11:04:55 PDT 2017
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$