Solucionar $x^3+x \equiv 1 \pmod p$

Question

Encontrar todos los números primos $p$, de modo que $$x^3+x \equiv 1 \pmod p \tag{1}$$ ha entero de soluciones.

Consideramos $x$ $y$ son las mismas soluciones iff $x\equiv y \pmod p.$

Podemos comprobar que la $(1)$ no tienen exactamente $2$ soluciones menos $p=31$. Al $p=31$, las soluciones de $(1)$ $x \equiv {17\text{ (double), } 28} \pmod {31}.$

Mi pregunta es: ¿cuándo $(1)$ no tienen solución, y cuando no $(1)$ ha $1$ solución y cuando no $(1)$ ha $3$ soluciones? (Como Ma Ming ha señalado, una ecuación de grado $3$ no tiene más de $3$ soluciones.)

Me han demostrado que si $p \not = 31$, e $a$ es una solución de $(1)$, $(1)$ $3$ soluciones iff $$\left(\frac{a-1}{p} \right)=\left(\frac{a+3}{p} \right),$$ aquí $\left( \frac{a}{p} \right)$ es el símbolo de Jacobi. Gracias de antemano!

Answer 1

Fuente, Hudson y Williams (1991). Tengo un pdf. La misma información, organizado por el tamaño de la discriminante, es en los apéndices de un libro de Henri Cohen, con la restricción de que deben ser campo discriminantes. También han pdf de eso.

$$\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 $un 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$ señales, a veces, porque estoy preocupado de que un estudiante de escribir programas de computación para este podría erróneamente tomar todas las variables no negativas.

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

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$ 

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

Answer 2

Para aumentar las respuestas de Pete Clark y Jagy: la división de campo de $x^3 + x - 1$ es la de Hilbert Campo de la Clase de $\mathbb Q(\sqrt{-31})$. Como Pete señaló, su grupo de Galois sobre $\mathbb Q$ es isomorfo a $S_3$. Así, la división de comportamiento de un primer $p$ depende en primer lugar de si es un cuadrado o no mod $31$, y (si es un cuadrado) o si no se divide, principalmente, en $\mathbb Q(\sqrt{-31})$; este es el origen teórico de la cuadrática de las formas que aparecen en Le Jagy la respuesta.

Si integramos $S_3$ a $GL(2,\mathbb C)$ en la forma habitual, y luego vamos a conseguir una de dos dimensiones Galois representación cuya división de campo es, precisamente, el la división de campo de la que estamos discutiendo, y que se corresponden (a través de la interpretación moderna de los resultados de Hecke) a una forma modular en $\Gamma_1(31)$ de los cuadrática nebentypus, la cual se puede escribir como una diferencia de funciones theta (asociada a la quad. las formas en Se Jagy la respuesta).

Así que hay una cierta $q$-expansión $\sum_{n = 1}^{\infty} a_n q^n$ con entero coeficientes de $a_n$ tal que $x^3 + x - 1$ divisiones de mod $p$ (diferente de $31$) si y sólo si $a_p = 2$. (A priori, $a_p = 0,-1$ o $2$.)

Si le hubieras preguntado a la pregunta correspondiente para $x^3 - x + 1$, cuyo discriminante es igual a $-23$, luego la misma historia sería la de aplicar (con $31$ reemplazado por $23$ en todas partes), y que podría haber dado la siguiente fórmula para el $q$-expansión, es decir,$q \prod_{n = 1}^{\infty} (1-q^n)(1-q^{23 n})$. E. g. en este caso la primera $p$ tal que $a_p = 2$ (y, por tanto, que el $x^3 - x + 1$ divisiones de mod $p$)$p = 59$.

En el caso de $-31$, aunque, no sé, una fórmula simple para la $q$-expansión, a pesar de que sin duda puede calcular cualquier número de términos de lo que quieras, utilizando las formas modulares de software.

Answer 3

El discriminante de la irreductible entero polinomio $f(x) = x^3+x-1$$-31$. Por lo tanto (como has dicho) no se repetirá raíces iff $p = 31$.

Deje $F = \mathbb{Q}[x]/(x^3+x-1)$. El cúbicos campo de número de $F$ no es Galois; por lo tanto su Galois cierre de $M$ $S_3$- extensión de la $\mathbb{Q}$. Por básicos de la teoría algebraica de números, la división de patrón de $f(x)$ modulo $p$ corresponde a la división patrón del primer ideal $(p)$$F$. Por ejemplo, tenemos tres raíces iff $p$ se divide completamente, y tiene exactamente una raíz iff $p \mathbb{Z}_F = \mathfrak{p}_1 \mathfrak{p}_2$ donde $\mathfrak{p}_1$ es un grado a un primer y $\mathfrak{p}_2$ es un grado dos primeros.

Además, por la Cebotarev Densidad Teorema uno puede calcular las densidades de estos conjuntos de números primos, pasando el cierre de Galois $M$. Un primer divide completamente en un campo de número de iff se divide completamente en su Galois de cierre --, equivalentemente, cada Frobenius elemento más de $p$ es trivial, y por Cebotarev Densidad en el conjunto de los números primos tiene una densidad de $\frac{1}{6}$. Un primer $p \neq 31$, que permanece inerte en $F$ debe dividir en dos grados $3$ de los números primos en $M$, ya que de lo contrario tendríamos una orden $6$ Frobenius elemento más de $p$ $S_3$ contiene ningún elemento de orden $6$. Por Cebotarev, la densidad del conjunto de los números primos es igual a la proporción de $3$-ciclos en $S_3$, lo $\frac{1}{3}$. El último caso es (sólo) un poco más complicada que las demás, pero podemos saltar desde las densidades deben agregar a $1$. Por lo tanto:

$\bullet$ Si $p = 31$, $f$ tiene raíces múltiples modulo $p$. De lo contrario, tiene claras raíces en $\overline{\mathbb{F}}_p$.

$\bullet$ El conjunto de los números primos $p$ tal que $f$ tiene tres raíces modulo $p$ tiene una densidad de $\frac{1}{6}$.

[Nota de que el más ingenuo supongo que habría sido de $\frac{1}{3}$. Uno realmente tiene que pasar a la Galois de cierre para aplicar Cebotarev!]

$\bullet$ El conjunto de los números primos $p$ tal que $f$ tiene una raíz modulo $p$ tiene una densidad de $\frac{1}{2}$.

$\bullet$ El conjunto de los números primos $p$ tal que $f$ no tiene raíces modulo $p$ tiene una densidad de $\frac{1}{3}$.

Ahora usted puede preguntar por qué sólo estoy diciendo que las densidades de estos diversos conjuntos en lugar de decirle que de manera más explícita que los primos de caer en que. La respuesta es que cuando el grupo de Galois del polinomio es nonabelian-como aquí-en general habrá no más simple descripción de los números primos de los de arriba Cebotarev condiciones. En contraste, cuando el polinomio tiene abelian Galois grupo de los conjuntos de números primos simplemente puede ser dada por la congruencia de las condiciones. Por ejemplo, yo azar encontró este folleto que trata la apariencia similar polinomio $x^3-3x-1$, pero este polinomio tiene cíclico grupo de Galois, que hace toda la diferencia en el mundo.

Es cierto que en determinadas circunstancias se pueden encontrar descripciones explícitas sobre los números primos que son un poco más complicado que la congruencia condiciones. A veces salen en términos de mayores residuos y a veces salen en términos de las formas modulares! Pero al mejor de mi conocimiento (y me gustaría tener más conocimientos aquí) este es más bien esporádicos y de la suerte; la parte superior de mi cabeza no estoy seguro de que este tipo de niza descripción existe aquí.