Loading [MathJax]/extensions/TeX/mathchoice.js

5 votos

Qué primos p dividir qq1 para un divisor primo q de p1

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 p1 tal que p divide qq1 .

7 por ejemplo, no es uno de estos primos ya que 7 no divide 221 o 331 . 11 es un buen ejemplo ya que 11 divide 221 o 551 .

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

0 votos

Si p1 tiene n factores primos- {q1qn} , debería p dividir (qqii1)  i{1,,n} ?

0 votos

Primer arreglo q y considerar un factor primo p de qq1 que es mayor que p . Entonces q divide p1 . Por ejemplo: q=3,p=13 .

0 votos

@arctictern Creo que OP quiere decir "al menos un primo". Ten en cuenta que p1 será uniforme, pero p no dividirá 221 . (Excepto en el caso de p=3 ).

3voto

Ataulfo Puntos 3108

Hay 168 primos p<1000 y quieres elegir entre todos ellos p tal que para al menos un primo q divisor de p1 uno tiene p divide qq1 . Así que quieres tener en el campo Fp la igualdad qq=1 Está claro que hay que probar sólo los factores primos q de p1 tal que qq1p 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 F997

996=22383 por lo que 2 y 3 se descartan y hay que calcular 8383=x Si x=1 entonces (997,83) es uno de los ejemplos requeridos y si x1 descartamos el primer p=997 . Tenemos 8383=(8320)4(83)3=(16)4506=1 por lo que se descarta el primer 997 .

2) En el campo F991 .

990=232511 por lo que tenemos que resolver 55=x and 1111=x {55=xx=1521111=xx=766 por lo que se descarta el primer 991 .

3) En el campo F983 .

982=2491 por lo que debemos resolver 491491=x Utilizando las igualdades 49110=24 , 249=22 y 2422=25 en F983 , uno tiene 491491=(24)49491=(2422)2((24)5491=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 qq+1 en lugar de qq1 , entonces los primos 997 y 983 han tenido en cuenta. ¿De dónde viene su problema?

0 votos

Estaba estudiando este problema para comprobar los divisores de qq1 y descubrió que, a excepción de q1 y q , todos los divisores r de qq1 = 1 \pmod q . Entonces se encontró que sólo unos pocos primos p dividir q^q-1 con q primo y la mayoría no lo hace. Con q^q+1 Esto añadiría más primos con el criterio anterior. Todos los primos de Sophie Germain se dividen q^q-1 o q^q+1 para algún primo q .

0 votos

El gran problema, J. Linne, es que no hay un criterio para encontrar los factores de p-1 y cuando se toman algunos grandes p aparecerá, sin duda, una gran prima q (dividiendo p-1 ) por lo que hay que probar con q^q-1\equiv 0\pmod p que es, en cada caso, una cuestión distinta de cálculo duro. La buena noticia es que para muchos primos el factor correspondiente q puede ser pequeño por lo que se descarta a primera vista pero los primos a mantener son absolutamente impredecibles por lo tanto "una fórmula" la veo muy fuera de alcance. Ojalá me equivoque. Suerte.

2voto

Jorrit Reedijk Puntos 129

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

0 votos

Estas calculadoras son maravillosas. Me gustaría aprender a manejarlas.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X