Solve $x^3+x \equiv 1 \pmod p$

Question

Find all the primes $p$ so that $$x^3+x \equiv 1 \pmod p \tag{1}$$ has integer solutions.

We consider $x$ and $y$ are the same solutions iff $x\equiv y \pmod p.$

We can prove that $(1)$ cannot have exactly $2$ solutions unless $p=31$. When $p=31$, the solutions of $(1)$ are $x \equiv {17\text{ (double), } 28} \pmod {31}.$

My question is: when does $(1)$ have no solution, and when does $(1)$ have $1$ solution and when does $(1)$ have $3$ solutions? (As Ma Ming has pointed out, an equation of degree $3$ has no more than $3$ solutions.)

I have proved that if $p \not = 31$, and $a$ is a solution of $(1)$, then $(1)$ has $3$ solutions iff $$\left(\frac{a-1}{p} \right)=\left(\frac{a+3}{p} \right),$$ here $\left( \frac{a}{p} \right)$ is the Jacobi symbol. Thanks in advance!

Answer 1

To augment the answers of Pete Clark and Will Jagy: the splitting field for $x^3 + x - 1$ is the Hilbert Class Field of $\mathbb Q(\sqrt{-31})$. As Pete noted, its Galois group over $\mathbb Q$ is isomorphic to $S_3$. Thus the splitting behaviour of a prime $p$ depends first on whether is is a square or not mod $31$, and (if it is a square) whether or not it splits principally in $\mathbb Q(\sqrt{-31})$; this is the theoretical origin of the quadratic forms appearing in Will Jagy's answer.

If we embed $S_3$ into $GL(2,\mathbb C)$ in the usual way, then we will get a two-dimensional Galois representation whose splitting field is precisely the splitting field we are discussing, and it will correspond (via the modern interpretation of results of Hecke) to a modular form on $\Gamma_1(31)$ of quadratic nebentypus, which one can write down as a difference of theta functions (associated to the quad. forms in Will Jagy's answer).

So there is a certain $q$-expansion $\sum_{n = 1}^{\infty} a_n q^n$ with integer coefficients $a_n$ such that $x^3 + x - 1$ splits mod $p$ (different from $31$) if and only if $a_p = 2$. (A priori, $a_p = 0,-1$, or $2$.)

If you had asked the corresponding question for $x^3 - x + 1$, whose discriminant equals $-23$, then the same story would apply (with $31$ replaced by $23$ everywhere), and I could have given you the following formula for the $q$-expansion, namely $q \prod_{n = 1}^{\infty} (1-q^n)(1-q^{23 n})$. E.g. in this case the first $p$ such that $a_p = 2$ (and hence such that $x^3 - x + 1$ splits mod $p$) is $p = 59$.

In the case of $-31$, though, I don't know a simple formula for the $q$-expansion, although you can certainly compute any number of terms of it that you want using modular forms software.

Answer 2

The discriminant of the irreducible integer polynomial $f(x) = x^3+x-1$ is $-31$. Thus (as you've said) there will be repeated roots iff $p = 31$.

Let $F = \mathbb{Q}[x]/(x^3+x-1)$. The cubic number field $F$ is not Galois; thus its Galois closure $M$ is an $S_3$-extension of $\mathbb{Q}$. By basic algebraic number theory, the splitting pattern of $f(x)$ modulo $p$ corresponds to the splitting pattern of the prime ideal $(p)$ in $F$. For instance we have three roots iff $p$ splits completely, and we have exactly one root iff $p \mathbb{Z}_F = \mathfrak{p}_1 \mathfrak{p}_2$, where $\mathfrak{p}_1$ is a degree one prime and $\mathfrak{p}_2$ is a degree two prime.

Further, by the Cebotarev Density Theorem one can compute the densities of these sets of primes by passing to the Galois closure $M$. A prime splits completely in a number field iff it splits completely in its Galois closure -- equivalently every Frobenius element over $p$ is trivial, and by Cebotarev Density the set of such primes has density $\frac{1}{6}$. A prime $p \neq 31$ which remains inert in $F$ must split into two degree $3$ primes in $M$, since otherwise we would have an order $6$ Frobenius element over $p$ and $S_3$ contains no element of order $6$. By Cebotarev, the density of the set of such primes is equal to the proportion of $3$-cycles in $S_3$, so $\frac{1}{3}$. The last case is (just) a little messier than the others, but we can skip it since the densities must add to $1$. Thus:

$\bullet$ If $p = 31$, $f$ has a multiple root modulo $p$. Otherwise it has distinct roots in $\overline{\mathbb{F}}_p$.

$\bullet$ The set of primes $p$ such that $f$ has three roots modulo $p$ has density $\frac{1}{6}$.

[Note that the more naive guess would have been $\frac{1}{3}$. One really does have to pass to the Galois closure to apply Cebotarev!]

$\bullet$ The set of primes $p$ such that $f$ has one root modulo $p$ has density $\frac{1}{2}$.

$\bullet$ The set of primes $p$ such that $f$ has no roots modulo $p$ has density $\frac{1}{3}$.

Now you may ask why I am only telling you the densities of these various sets rather than telling you more explicitly which primes fall into which. The answer is that when the Galois group of the polynomial is nonabelian -- as here -- there will in general be no simpler description of the primes than the above Cebotarev conditions. In contrast, when the polynomial has abelian Galois group the sets of primes can simply be given by congruence conditions. For instance, I randomly found this handout which treats the similar looking polynomial $x^3-3x-1$ instead, but this polynomial has cyclic Galois group, which makes all the difference in the world.

It is true that in certain circumstances one can find explicit descriptions on the primes which are a bit more complicated than just congruence conditions. Sometimes they come out in terms of higher residues and sometimes they come out in terms of modular forms! But to the best of my knowledge (and I wish I had more knowledge here) this is rather sporadic and lucky; off the top of my head I'm not sure that this kind of nice description exists here.

Answer 3

Source, Hudson and Williams (1991). I have a pdf. The same information, organized by size of discriminant, is in the appendices of a book by Henri Cohen, with the restriction that they need to be field discriminants. Also have pdf of that.

$$\begin{array}{l}\text{Hath not a quadratic form eyes? Hath not a quadratic form hands, organs,}\cr \text{dimensions, senses, affections, passions; fed with}\cr \text{the same food, hurt with the same weapons, subject}\cr \text{to the same diseases, heal'd by the same means,}\cr \text{warm'd and cool'd by the same winter and summer}\cr \text{as an algebraic number field is? If you prick us, do we not bleed?}\end{array}$$

Two roots: $$ p = 31$$

Three roots: $$ p\neq 31, \; \; \; \; p = u^2 + u v + 8 v^2$$

No roots: $$ p = 2 u^2 + uv + 4 v^2 $$

One root: $$ (-31 | p) = -1 $$

This was a favorite result of Kronecker, see page 88 in David A. Cox, Primes of the Form $x^2 + n y^2.$ You do need to know, for this, that $x^2 + 31 y^2 $ and $u^2 + u v + 8 v^2$ represent the same ODD NUMBERS, including any primes other than 2. Similarly, $5 x^2 + 4 x y + 7 y^2 $ and $2 u^2 + u v + 4 v^2$ represent the same ODD NUMBERS, including any primes other than 2. In case this is unfamiliar, in order to make a group under Gauss composition, we distinguish between $a x^2 + b x y + c y^2$ and $a x^2 - b x y + c y^2,$ although they represent exactly the same numbers integrally. They are inverses in the class group. I write in $\pm$ signs sometimes, because I am worried that a student writing computer programs for this might mistakenly take all variables non-negative.

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

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ date
    Wed May  1 11:48:02 PDT 2013
    jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 
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? 
1000

          p          mod 31
          31           0
          47          16
          67           5
         131           7
         149          25
         173          18
         227          10
         283           4
         293          14
         349           8
         379           7
         431          28
         521          25
         577          19
         607          18
         617          28
         653           2
         811           5
         839           2
         853          16
         857          20
         919          20
         937           7
         971          10


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

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 
    jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 
    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 
2 1 4
Discriminant  -31

Modulus for arithmetic progressions? 
31
Maximum number represented? 
1000
          p          mod 31
           2           2
           5           5
           7           7
          19          19
          41          10
          59          28
          71           9
          97           4
         101           8
         103          10
         107          14
         109          16
         113          20
         157           2
         163           8
         191           5
         193           7
         211          25
         233          16
         257           9
         281           2
         307          28
         311           1
         317           7
         359          18
         373           1
         397          25
         419          16
         421          18
         439           5
         443           9
         467           2
         479          14
         503           7
         541          14
         547          20
         563           5
         593           4
         599          10
         659           8
         661          10
         683           1
         691           9
         701          19
         727          14
         733          20
         751           7
         769          25
         877           9
         887          19
         907           8
         977          16
         997           5


    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
    Wed May  1 12:07:28 PDT 2013
    jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 

THREE

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./rootmod
       47          12          13          22
       67           4           9          54
      131          56          80         126
      149          11          56          82
      173           8          37         128
      227          22          24         181
      283          34          67         182
      293          37          42         214
      349           7         102         240
      379         186         255         317
      431          75         384         403
      521          86         443         513
      577          72         161         344
      607         118         515         581
      617         190         447         597
      653         114         255         284
      811          90         134         587
      839         403         526         749
      853         121         326         406
      857         336         548         830
      919          14         257         648
      937         232         340         365
      971         281         748         913
    jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 


ZERO

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./rootmod
        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
    jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 

ONE

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 
    jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./rootmod
    3           2
   11           9
   13           6
   17           6
   23          19
   29           3
   37          12
   43           5
   53          17
   61          24
   73          50
   79          68
   83          48
   89          75
  127          41
  137          71
  139          34
  151          30
  167         144
  179          30
  181          41
  197          64
  199          89
  223         217
  229          62
  239          23
  241         194
  251         162
  263         182
  269          66
  271         149
  277         240
  313         149
  331         230
  337         327
  347          62
  353          99
  367         110
  383         133
  389         142
  401         244
  409         315
  433         142
  449         128
  457         441
  461         225
  463         303
  487         355
  491          97
  499         314
  509         147
  523         409
  557         374
  569         431
  571          50
  587         119
  601         219
  613         387
  619         390
  631         385
  641          57
  643         513
  647          72
  673         606
  677         583
  709          28
  719         337
  739         730
  743         160
  757         383
  761         290
  773         382
  787         320
  797         560
  809         609
  821         318
  823         614
  827         592
  829         665
  859         394
  863         205
  881         845
  883          74
  911         833
  929         490
  941         428
  947         614
  953         279
  967         298
  983         823
  991         368
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 

     TWO

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 
    jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./rootmod
   31          17          28
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 

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