Roots of a cubic mod prime

Question

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

Answer 1

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. :)

Answer 2

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$

Answer 3

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$ 

Answer 4

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