Qué primos $p$ dividir $q^q-1$ para un divisor primo $q$ de $p-1$

Question

Estoy buscando (una fórmula) para todos los primos $p$ menor o igual a $X$ con los siguientes criterios:

Hay al menos un primo $q$ dividiendo $p-1$ tal que $p$ divide $q^q-1$ .

$7$ por ejemplo, no es uno de estos primos ya que $7$ no divide $2^2-1$ o $3^3-1$ . $11$ es un buen ejemplo ya que $11$ divide $2^2-1$ o $5^5-1$ .

Lo que prima $p$ son estos menos que $1000$ por ejemplo. Gracias por la ayuda.

Answer 1

Hay $168$ primos $p\lt 1000$ y quieres elegir entre todos ellos $p$ tal que para al menos un primo $q$ divisor de $p-1$ uno tiene $p$ divide $q^q-1$ . Así que quieres tener en el campo $\mathbb F_p$ la igualdad $$q^q=1$$ Está claro que hay que probar sólo los factores primos $q$ de $p-1$ tal que $q^q-1\ge p$ Por lo tanto, cuando $p$ aumenta, se pueden descartar los factores primos pequeños $q$ .

A la espera de una respuesta teórica ( lo que me parece difícil de hecho ) Aquí muestro lo que puedo hacer para los tres más grandes, $983,991$ y $997$ de los primos en cuestión antes de dar algunos comentarios finales sobre su problema.

1) En el campo $\mathbb F_{997}$

$996=2^2\cdot3\cdot83$ por lo que $2$ y $3$ se descartan y hay que calcular $$83^{83}=x$$ Si $x=1$ entonces $(997,83)$ es uno de los ejemplos requeridos y si $x\ne 1$ descartamos el primer $p=997$ . Tenemos $$83^{83}=(83^{20})^4(83)^3=(16)^4\cdot 506=-1$$ por lo que se descarta el primer $997$ .

2) En el campo $\mathbb F_{991}$ .

$990=2\cdot3^2\cdot5\cdot11$ por lo que tenemos que resolver $$5^5=x \text{ and } 11^{11}=x$$ $$\begin{cases}5^5=x\Rightarrow x=152\\11^{11}=x\Rightarrow x=766\end{cases}$$ por lo que se descarta el primer $991$ .

3) En el campo $\mathbb F_{983}$ .

$982=2\cdot 491$ por lo que debemos resolver $$491^{491}=x$$ Utilizando las igualdades $491^{10}=24$ , $24^9=22$ y $24^{22}=25$ en $\mathbb F_{983}$ , uno tiene $$491^{491}=(24)^{49}\cdot 491=(24^{22})^2((24)^5\cdot 491=-1$$

por lo que se descarta el primo $983$ . $$****$$ Si no hay errores de cálculo, no hay que guardar ninguno de los tres primos considerados. Queda $165$ primos para comprobar dónde, por ejemplo, para $p=887$ tienes el factor $q=443$ de $886$ , para $p=863$ el factor $q=431$ y para $p=839$ el factor $q=419$ lo que lleva a cálculos no inmediatos a resolver como para el primo ya descartado $p = 983$ .

Una última observación es que si hubieras pedido $q ^ q + 1$ en lugar de $q^q-1$ , entonces los primos $997$ y $983$ han tenido en cuenta. ¿De dónde viene su problema?

Answer 2

Sólo para aportar algo más que un puñado de datos.
1) Este es el código que he utilizado en Pari/GP :

  list=vectorv(1000);li=0;
 {forprime(p=2,11333, \\  11333 is just a "idle-typing" value
    f=factor(p-1); 
    for(k=1,rows(f),
          q=f[k,1]; 
          if((q^q-1) % p == 0 ,
                 li++;list[li]=[p,q,(p-1)/q ]
        ))
     );}
   list=Mat(VE(list,li))      \\ VE is a private short from for "vecextract"
   listso = vecsort(list~,[3,1])~ 

2) Esta es la tabla de datos ordenada (nota, que no encontré ninguno $p$ con dos soluciones $q$ ) :

      p     q   (p-1)/q
   ---------------------
      3     2    1
     11     5    2
     59    29    2
     83    41    2
    107    53    2
    179    89    2
    227   113    2
    347   173    2
    467   233    2
    563   281    2
    587   293    2
   1019   509    2
   1187   593    2
   1283   641    2
   1307   653    2
   1523   761    2
   1619   809    2
   1907   953    2
   2027  1013    2
   2099  1049    2
   2459  1229    2
   2579  1289    2
   2819  1409    2
   2963  1481    2
   3203  1601    2
   3467  1733    2
   3779  1889    2
   3803  1901    2
   3947  1973    2
   4139  2069    2
   4259  2129    2
   4283  2141    2
   4547  2273    2
   4787  2393    2
   5099  2549    2
   5387  2693    2
   5483  2741    2
   5507  2753    2
   5939  2969    2
   6659  3329    2
   6779  3389    2
   6827  3413    2
   6899  3449    2
   7187  3593    2
   7523  3761    2
   7643  3821    2
   8147  4073    2
   8699  4349    2
   8747  4373    2
   8819  4409    2
   8963  4481    2
   9467  4733    2
   9587  4793    2
  10163  5081    2
  10667  5333    2
  10883  5441    2
  11003  5501    2
     13     3    4
     29     7    4
     53    13    4
    149    37    4
    173    43    4
    269    67    4
    293    73    4
    317    79    4
    389    97    4
    509   127    4
    557   139    4
    653   163    4
    773   193    4
    797   199    4
   1109   277    4
   1229   307    4
   1493   373    4
   1637   409    4
   1733   433    4
   1949   487    4
   1997   499    4
   2309   577    4
   2477   619    4
   2693   673    4
   2837   709    4
   2909   727    4
   2957   739    4
   3413   853    4
   3533   883    4
   3677   919    4
   3989   997    4
   4133  1033    4
   4157  1039    4
   4253  1063    4
   4349  1087    4
   4373  1093    4
   4493  1123    4
   4517  1129    4
   5189  1297    4
   5309  1327    4
   5693  1423    4
   5717  1429    4
   5813  1453    4
   6173  1543    4
   6197  1549    4
   6269  1567    4
   6317  1579    4
   6389  1597    4
   6653  1663    4
   7013  1753    4
   7109  1777    4
   7517  1879    4
   7949  1987    4
   8069  2017    4
   8117  2029    4
   8573  2143    4
   9173  2293    4
   9533  2383    4
   9749  2437    4
  10589  2647    4
  10709  2677    4
  10733  2683    4
  10853  2713    4
  11069  2767    4
  11213  2803    4
    439    73    6
    607   101    6
   1087   181    6
   1399   233    6
   1447   241    6
   2239   373    6
   2383   397    6
   3343   557    6
   3559   593    6
   3607   601    6
   3919   653    6
   5119   853    6
   6079  1013    6
   7159  1193    6
   8887  1481    6
   9319  1553    6
   9679  1613    6
  11239  1873    6
   1049   131    8
   1097   137    8
   1193   149    8
   3833   479    8
   4457   557    8
   4937   617    8
   6569   821    8
   7577   947    8
   7817   977    8
   9209  1151    8
  10457  1307    8
  10889  1361    8
   1931   193   10
   3491   349   10
   7331   733   10
  10331  1033   10
    709    59   12
   1213   101   12
   1237   103   12
   2797   233   12
   3373   281   12
   5557   463   12
   9277   773   12
  11149   929   12
     71     5   14
   4943   353   14
    977    61   16
   2417   151   16
   2609   163   16
   2897   181   16
   4337   271   16
   5009   313   16
   6737   421   16
   8753   547   16
  10289   643   16
  10243   569   18
    461    23   20
   2617   109   24
   8377   349   24
  11117   397   28
   3391   113   30
   2657    83   32
   1693    47   36
   1999    37   54
   1289    23   56
   5657   101   56
   4021    67   60
   8363   113   74
   7993    37  216
  10949    17  644
   4733     7  676