4
$\begingroup$

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

  • 0
    I think you need to compute the discriminant of the polynomial in $\mathbb{Q}$.2012-08-05

4 Answers 4

8

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

  • 2
    I'd say the field of $\cos(2\pi/7)$ is tied for simplest abelian cubic with the field of $\cos(2\pi/9)$.2012-08-05
1

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$ 
1

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$  
  • 0
    @paulgarrett, we are put on Earth to amuse those around us.2012-08-06
0

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