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

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!

• A equation of degree $d$ has no more than $d$ solutions. – Ma Ming May 1 '13 at 15:39
• @Ma Ming,thanks,I mean when does (1) has no solution,and when does (1) has 1 solution and when does (1) has 3 solutions:) – Next May 1 '13 at 15:42
• Dear Sophie, This is a rather sophisticated question, or at least, has a sophisticated answer. Where did you come across it? Regards, – Matt E May 1 '13 at 20:21
• – Watson May 13 '18 at 19:28

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.

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.

• Is there any example for "explicit descriptions" in the last paragraph? I'm curious to see examples for nonabelian extensions. – user27126 May 1 '13 at 18:37
• @Sanchez: happily, it turns out that both Will Jagy and Matt E have given descriptions of the sort I had in mind in this case. – Pete L. Clark May 2 '13 at 1:44

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$


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