# Roots of a cubic mod prime

For which primes $p$ is there a root to the equation $x^3+x^2-2x-1$ mod $p$? I have no idea where to start, any help is appreciated! Thank you

-
A place to start is just trying some primes (by hand, or with a computer) and looking for patterns. Usually this technique doesn't work very well, but it is better than doing nothing. – huon Aug 5 '12 at 19:56
I think you need to compute the discriminant of the polynomial in $\mathbb{Q}$. – Makoto Kato Aug 5 '12 at 20:01

This is a bit of a trick question, for the following reason. First, if we approach this question "honestly", and ask about generic cubics, there is not much one can say at an elementary level, in part (indirectly) because the Galois group over $\mathbb Q$ is probably not abelian (so, secretly, "classfield theory", the well-developed study of questions of this sort for abelian extensions would not apply).

However, since the question is asked at all, one might suspect that the Galois group over $\mathbb Q$ is abelian. Both because one is disinclined to compute a discriminant of a cubic, and because one suspects that the polynomial is special, anyway, my reaction is to wonder whether it's the simplest cubic I know with abelian Galois group over $\mathbb Q$, namely, that for the cubic subfield of the field of seventh roots of unity (with cyclic Galois group of order $6$, so admitting a unique cubic subfield).

Indeed, a standard trick going back at least 240 years: from $x^6+x^5+\ldots+x+1=0$, dividing through by $x^3$, gives $x^3+x^2+x+1+x^{-1}+x^{-2}+x^{-3}=0$. Letting $y=x+x^{-1}$, we find $y^3+y^2-2y-1=0$. [Edit: terrible typo: the $y^2$ term was earlier written just as $y$. Sorry!]

Thus, that cubic factoring means there is a linear factor, so a seventh root of unity is at most quadratic over $\mathbb F_p$. That is, either there is a seventh root of $1$ in $\mathbb F_p$ already, which is $7|(p-1)$, or in the quadratic extension, so $7|(p^2-1)$. The latter condition subsumes the former, so the condition is $7|(p^2-1)$, which is $p=\pm 1\mod 7$, since $7$ is prime.

Edit-edit: as in commments by Will Jagy, the cubic $x^3+x^2-4x+1$ apparently is a cubic with roots in the unique cubic subfield of 13th cyclotomic field. :)

Edit-edit-edit: indeed, as Gerry M notes, the 9th roots of unity have an arguably even simpler cubic subfield. And/but we'd recognize that cubic, indeed. Maybe future generations will all recognize the cubic subfields of 7th and 13th roots. :)

-
How about this polynomial $X^3+X^2-4X+1$? – Makoto Kato Aug 5 '12 at 20:21
About $x^3+x^2-4x+1$, I'd see (having just recomputed the seventh-root case) that it's not the seventh root cubic, so I'd hope that maybe it's for the cubic subfield of the thirteenth cyclotomic field, but it'd be much more work to determine that, and then I might decide it'd be less work to compute the discriminant... thereby indirectly finding out (by Kronecker-Weber!) which cyclotomic field it's inside. More work than the present fortunate example! – paul garrett Aug 5 '12 at 20:52
There is a root for $p = 7$ ($x=2$) too. How does this fit in? – huon Aug 5 '12 at 21:02
Oop, yes, $7$ is special for this story: $x^7-1=(x-1)^7 \mod 7$, so the roots are all $1$. Thus, the computation above found the/a cubic satisfied by the sum of a root and its inverse, which, mod $7$, is $1+1^{-1}=2$. – paul garrett Aug 5 '12 at 21:15
I'd say the field of $\cos(2\pi/7)$ is tied for simplest abelian cubic with the field of $\cos(2\pi/9)$. – Gerry Myerson Aug 5 '12 at 23:32

Just some computer runs. The point here is that the discriminants are positive and squares. Meanwhile, disc 49 first,

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$./rootmod cubic x^3 + x^2 - 2 x - 1, discriminant = 49. p p % 7 roots, if any 2 2 3 3 5 5 7 0 2 11 4 13 6 7 8 10 17 3 19 5 23 2 29 1 3 7 18 31 3 37 2 41 6 14 30 37 43 1 8 15 19 47 5 53 4 59 3 61 5 67 4 71 1 4 14 52 73 3 79 2 83 6 10 15 57 89 5 97 6 25 30 41 101 3 103 5 107 2 109 4 113 1 9 24 79 127 1 24 36 66 131 5 137 4 139 6 5 23 110 149 2 151 4 157 3 163 2 167 6 19 25 122 173 5 179 4 181 6 37 43 100 191 2 193 4 197 1 95 140 158 199 3 jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$


Next, preferably a separate code block, disc 169, we get (except for 13 itself) roots when $p \equiv 1,5,8,12 \pmod {13}$

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$./rootmod cubic x^3 + x^2 - 4 x + 1, discriminant = 169. p p % 13 roots, if any 2 2 3 3 5 5 2 3 4 7 7 11 11 13 0 4 17 4 19 6 23 10 29 3 31 5 9 25 27 37 11 41 2 43 4 47 8 22 33 38 53 1 20 39 46 59 7 61 9 67 2 71 6 73 8 7 12 53 79 1 17 66 74 83 5 37 53 75 89 11 97 6 101 10 103 12 54 68 83 107 3 109 5 8 31 69 113 9 127 10 131 1 5 27 98 137 7 139 9 149 6 151 8 80 86 135 157 1 20 33 103 163 7 167 11 173 4 179 10 181 12 28 67 85 191 9 193 11 197 2 199 4 211 3 223 2 227 6 229 8 6 39 183 233 12 107 136 222 239 5 38 45 155 241 7 251 4 257 10 263 3 269 9 271 11 277 4 281 8 31 103 146 283 10 293 7 jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$

-

Discriminant $361 = 19^2,$ I got roots for $p \equiv 1,7,8,11,12,18 \pmod{19}.$ Then for discriminant $1369 = 37^2,$ I got roots for $p \equiv 1,6,8,10,11,14,23,26,27,29,31,36 \pmod{37}.$

Output for $19:$

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$./rootmod cubic x^3 + x^2 - 6 x - 7, discriminant = 361. p p % 19 roots, if any 2 2 3 3 5 5 7 7 0 2 4 11 11 1 3 6 13 13 17 17 19 0 6 23 4 29 10 31 12 15 19 27 37 18 14 29 30 41 3 43 5 47 9 53 15 59 2 61 4 67 10 71 14 73 16 79 3 83 7 43 58 64 89 13 97 2 101 6 103 8 41 74 90 107 12 9 30 67 109 14 113 18 5 15 92 127 13 131 17 137 4 139 6 149 16 151 18 37 119 145 157 5 163 11 12 23 127 167 15 173 2 179 8 95 108 154 181 10 191 1 109 116 156 193 3 197 7 11 80 105 199 9 211 2 223 14 227 18 71 184 198 229 1 19 101 108 233 5 239 11 57 80 101 241 13 251 4 257 10 263 16 269 3 271 5 277 11 93 219 241 281 15 283 17 293 8 28 99 165 307 3 311 7 97 236 288 313 9 317 13 331 8 56 96 178 337 14 347 5 349 7 87 113 148 353 11 161 205 339 359 17 367 6 373 12 50 115 207 379 18 113 121 144 383 3 389 9 397 17 jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$


Output for $37:$

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$./rootmod cubic x^3 + x^2 - 12 x + 11, discriminant = 1369. p p % 37 roots, if any 2 2 3 3 5 5 7 7 11 11 0 3 7 13 13 17 17 19 19 23 23 9 14 22 29 29 7 24 26 31 31 9 23 29 37 0 12 41 4 43 6 4 16 22 47 10 12 15 19 53 16 59 22 61 24 67 30 71 34 73 36 15 28 29 79 5 83 9 89 15 97 23 16 86 91 101 27 5 27 68 103 29 57 59 89 107 33 109 35 113 2 127 16 131 20 137 26 68 94 111 139 28 149 1 19 36 93 151 3 157 9 163 15 167 19 173 25 179 31 42 50 86 181 33 191 6 6 40 144 193 8 100 129 156 197 12 199 14 27 178 192 211 26 94 154 173 223 1 47 65 110 227 5 229 7 233 11 43 63 126 239 17 241 19 251 29 105 183 213 257 35 263 4 269 10 96 187 254 271 12 277 18 281 22 283 24 293 34 307 11 28 60 218 311 15 313 17 317 21 331 35 337 4 347 14 43 111 192 349 16 353 20 359 26 138 285 294 367 34 373 3 379 9 383 13 389 19 397 27 170 251 372 401 31 23 166 211 409 2 419 12 421 14 42 156 222 431 24 433 26 225 234 406 439 32 443 36 193 277 415 449 5 457 13 461 17 463 19 467 23 62 180 224 479 35 487 6 24 129 333 491 10 8 72 410 499 18 503 22 509 28 521 3 523 5 541 23 18 170 352 547 29 110 158 278 557 2 563 8 66 520 539 569 14 272 315 550 571 16 577 22 587 32 593 1 97 107 388 599 7 jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$

-
Fun data! :) ... – paul garrett Aug 6 '12 at 2:00
@paulgarrett, we are put on Earth to amuse those around us. – Will Jagy Aug 6 '12 at 2:01

Attempting to put a third set of tables. This time I left out the primes without roots. I just ran up to primes large enough to get at least two each of each residue class for which the cubic has roots. Anyway $p = 61, 79, 97.$

$$61^2 = 3721$$

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus\$ ./rootmod
cubic x^3  - 61 x + 183, discriminant = 3721.
p % 61    p      roots, if any
0      61       0
1     367      16     120     231
1     733      85     668     713
1     977     484     613     857
3    1223     353     387     483
3       3       0       1       2
3     491      53     156     282
3     613     101     531     594
3     857     156     346     355
8    1289     103     367     819
8     191      10      64     117
8     313      30     132     151
8     557      45     101     411
9    1229     624     640    1194
9     131      12      46      73
9     619      28     118     473
9     863     482     610     634
11    1109     126     348     635
11      11       6       7       9
11    1231     524     724    1214
11    1597     630    1018    1546
11     499     166     373     459
11     743     380     391     715
20    1301     707     757    1138
20    1423     572     970    1304
20     569     284     299     555
20     691      14      29     648
23    1487     814     953    1207
23      23       2       8      13
23     389     225     245     308
23     877     129     136     612
24    1061     417     710     995
24    1427     116     371     940
24    1549     311    1323    1464
27     149      18      41      90
27     271     129     154     259
27     881      15     118     748
28    1187     321     993    1060
28    1553      56     696     801
28     211      20      72     119
28     577      39     206     332
28     821     517     523     602
28      89      23      73      82
33    1009     540     637     841
33     277      85     221     248
33     521      48     120     353
33     643     213     509     564
33     887     363     657     754
34    1193     342     895    1149
34    1559      58     131    1370
34     461      88      91     282
34     827     481     572     601
37    1013     183     411     419
37     281      11     103     167
37      37      19      24      31
37     647      36     259     352
37     769     195     205     369
38    1319     203     277     839
38     587     279     428     467
38     709     431     460     527
38     953     136     863     907
41     163      88     108     130
41      41       1      17      23
41     773     438     527     581
50    1087      94     433     560
50    1453     215     407     831
50     233     108     159     199
50     599      26     126     447
52     113      24      92     110
52     479     131     374     453
52     601      76     164     361
52     967     140     283     544
53    1151     258     348     545
53     419      81      83     255
53      53      19      42      45
53     541      91     477     514
53     907      21     319     567
58    1217     267     360     590
58    1583     939     974    1253
58     241      46      76     119
58     607     352     429     433
60    1097     146    1001    1047
60     487      95     429     450
60     853     424     504     778


$$79^2 = 6241$$

cubic x^3 + x^2 - 26 x + 41, discriminant = 6241.
p % 79    p      roots, if any
0      79      26
1    1423      68     542     812
1     317     119     236     278
8    1193     650     817     918
8     719      97     285     336
8     877     112     179     585
10    1511     762    1081    1178
10     563      86     158     318
10      89      20      70      87
12    1039     122     229     687
12     881      10     113     757
14     251       7      53     190
14     409       8      71     329
14     883      71     822     872
15    1279      97     451     730
15     173      30      34     108
15     331      92     117     121
15     647     226     443     624
17    1123     649     713     883
17    1439     642    1080    1155
17    1597     546    1098    1549
17      17       1       4      11
17     491     135     400     446
18    1361     787     837    1097
18     571      42     160     368
18     887     339     611     823
18      97      16      84      93
21     179      83     134     140
21     337      18      24     294
21     653      78     150     424
21     811     402     593     626
22     101      19      84      98
22    1049     498     731     868
22    1523     855    1010    1180
22     733      78     217     437
27    1291     212     378     700
27     659     379     440     498
33    1297      28     417     851
33     191      31      77      82
33     349     184     189     324
33     823     306     624     715
38    1223     297    1027    1121
38    1381     749     848    1164
38     433      90     126     216
38     907      49     140     717
41     199      23     183     191
41      41       0      16      24
41     673     383     434     528
46    1231      91    1151    1219
46     283     146     190     229
46     599      53     555     589
46     757     153     219     384
52    1237     382    1004    1087
52     131      39      42      49
52    1553     710     907    1488
57    1163     148     234     780
57    1321     461     974    1206
57     373      37     344     364
58     137       6      37      93
58    1559     444     458     656
58     769     442     517     578
61    1009     263     320     425
61    1483     675     869    1421
61      61       5      23      32
62     457      39     167     250
62     773     175     213     384
64    1091     180     193     717
64    1249     383     426     439
64     617       9      91     516
65    1013     120     331     561
65    1171     644     751     946
65    1487     723     793    1457
65     223      26      68     128
67    1489     308     475     705
67     383     186     284     295
67     541      21      32     487
67      67      19      48      66
67     857     304     654     755
69     227     114     155     184
69     701     132     278     290
69     859     442     454     821
71    1019     195     890     952
71    1493     772    1083    1130
71     229      34      96      98
71      71      11      64      66
78     157      30      31      95
78    1579     720    1052    1385
78     631     314     454     493
78     947     295     769     829


$$97^2 = 9409$$

cubic x^3 + x^2 - 32 x - 79, discriminant = 9409.
p % 97    p      roots, if any
0      97      32
1    1553     152     517     883
1    1747     415    1498    1580
1     389     145     293     339
1     971     487     703     751
8    1657     128     464    1064
8    2239      56     706    1476
8     881     233     707     821
12     109       1      23      84
12    2243     509    1829    2147
12    2437     240     806    1390
12     691     101     201     388
18    1279     157    1133    1267
18    1667     891    1027    1415
18    1861     896    1089    1736
18     503     251     356     398
19    1571     638    1143    1360
19      19       6      14      17
19    2153    1045    1602    1658
19    2347     452     811    1083
19     601     162     493     546
20    1087     547     794     832
20    1669     589    1317    1431
20    2251     823    1788    1890
20     311     139     221     261
22    1283     422    1024    1119
22    2447     626     902     918
22     313      59     102     151
22     701      10      47     643
27    1579     266     459     853
27    2161     877    1481    1963
27     997     331     793     869
28    1289     202     216     870
28    1483     469     483     530
28    1871      13     107    1750
30    1097     250     295     551
30     127       4      14     108
30    1291     237    1131    1213
30    1873     966    1227    1552
30     709      49     104     555
33    1973     836    1240    1869
33     227      40      91      95
33     421     227     305     309
33     809      25     256     527
34     131       2      22     106
34    1489     580    1101    1296
34    1877     198     631    1047
34    2459      36    1165    1257
34     907      93     184     629
42    1109     429     855     933
42    1303      60     451     791
42     139       3      19     116
42    2273     152    2168    2225
42    2467     873    1942    2118
45    1597     104     593     899
45    2179     215    1977    2165
45     239     126     172     179
45     433      48     405     412
45     821     143     293     384
46    1307     717     878    1018
46    1889      33     888     967
46    2083      46      81    1955
46     337      32      73     231
46     919     124     277     517
47    1987     915    1154    1904
47     241       8      17     215
47      47      19      28      46
47     823     294     589     762
50    1117      57     238     821
50    1699     121     663     914
50    2087     124     372    1590
50    2281    1116    1221    2224
51    1021      11      65     944
51    1409      12      85    1311
51     439      85     362     430
51     827     407     587     659
52     149      47     108     142
52    2089     507     647     934
52    2477      78     873    1525
55    1607     561    1257    1395
55    1801     358     445     997
55    2383      77     909    1396
55     443       9      31     402
63    1033      41     489     502
63    2003     148     447    1407
63     257      48      81     127
63     839     344     660     673
64    1907     338     694     874
64     743     181     246     315
64     937     131     816     926
67    1231     323     974    1164
67    1619     319     403     896
67      67      31      41      61
69    1039     392     771     914
69    1427     729     883    1241
69    1621     555    1097    1589
69    2203     393     569    1240
69     263      37      42     183
69     457     139     144     173
70     167      49      57      60
70    1913     878    1114    1833
75    1433     163     263    1006
75    1627     148     286    1192
75     269     115     208     214
75     463      28     214     220
77    1823     273     767     782
77    2017    1042    1488    1503
77     271      65     213     263
77     659     107     561     649
77     853     211     279     362
78    2309     978    1420    2219
78     563     258     408     459
78     757     165     212     379
79    1049     121     309     618
79    2213     835    1562    2028
79     467     239     341     353
79     661      59     625     637
79      79       0      22      56
85    1249     140     422     686
85    1637     360     465     811
85    1831     804    1300    1557
89    1447     534     993    1366
89    2029     380     441    1207
89    2417     806    1856    2171
89     283      40      42     200
89      89       5       7      76
96    1163      73     435     654
96     193      37      77      78

-