Hay 168 primos p<1000 y quieres elegir entre todos ellos p tal que para al menos un primo q divisor de p−1 uno tiene p divide qq−1 . 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 p−1 tal que qq−1≥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 F997
996=22⋅3⋅83 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 x≠1 descartamos el primer p=997 . Tenemos 8383=(8320)4(83)3=(16)4⋅506=−1 por lo que se descarta el primer 997 .
2) En el campo F991 .
990=2⋅32⋅5⋅11 por lo que tenemos que resolver 55=x and 1111=x {55=x⇒x=1521111=x⇒x=766 por lo que se descarta el primer 991 .
3) En el campo F983 .
982=2⋅491 por lo que debemos resolver 491491=x Utilizando las igualdades 49110=24 , 249=22 y 2422=25 en F983 , uno tiene 491491=(24)49⋅491=(2422)2((24)5⋅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 qq+1 en lugar de qq−1 , entonces los primos 997 y 983 han tenido en cuenta. ¿De dónde viene su problema?
0 votos
Si p−1 tiene n factores primos- {q1⋯qn} , debería p dividir (qqii−1) ∀i∈{1,⋯,n} ?
0 votos
Primer arreglo q y considerar un factor primo p de qq−1 que es mayor que p . Entonces q divide p−1 . Por ejemplo: q=3,p=13 .
0 votos
@arctictern Creo que OP quiere decir "al menos un primo". Ten en cuenta que p−1 será uniforme, pero p no dividirá 22−1 . (Excepto en el caso de p=3 ).
0 votos
@ajotatxe Eso es lo que he dicho.
0 votos
Para su búsqueda, también podría fijar el factor r=(p−1)q . Por ejemplo, cuando r=2 , usted está mirando a los primos q tal que 2q+1 también es primo y q es 1 mod 4. Algunos ejemplos son q=5 , q=29 , q=41 que dan valores de p=11,59,83 .
0 votos
2 no cuenta ya que ningún primo divide a 1 . Los primeros primos menores que 30 con el siguiente criterio anterior son 3 , 11 , 13 y 29 dividiendo 22−1 , 55−1 , 33−1 , 77−1 .