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
Roots of a cubic mod prime
-
0I think you need to compute the discriminant of the polynomial in $\mathbb{Q}$. – 2012-08-05
4 Answers
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. :)
-
2I'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
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$
-
0@paulgarrett, we are put on Earth to amuse those around us. – 2012-08-06
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