Sé que $36^2 + 1$ es primo, $154^2 + 1$ no lo es, ambos son iguales a $1 \bmod 4$ . Los divisores primos de $154^2 + 1$ debe ser también de la forma $1 \bmod 4$ . Intenté mostrar esto mediante el teorema de Wilson, sin embargo no siento que esté llegando a ningún lado.
Respuestas
¿Demasiados anuncios?
Erick Wong
Puntos
12209
Mi mejor suposición sería que sólo quieren que hagas la división de prueba por primos $p = 5,13,17,\ldots$ hasta $36$ (hay muchos menos primos para probar con el $1$ mod $4$ restricción). Por ejemplo, para comprobar si $13$ divide $36^2+1$ se puede calcular $$ 36^2 + 1 \equiv (-3)^2 + 1 = 10 \not\equiv 0 \pmod{13}.$$
Para $154^2+1$ en el peor de los casos, podría tener que subir a $154$ pero en realidad se encuentra un factor primo mucho antes que esto (por debajo de $40$ ).
Stephan Aßmus
Puntos
16
Las raíces cuadradas de $-1 \pmod 5$ son $2,3 \pmod 5$ pero $154 \equiv 4 \pmod 5.$
Las raíces cuadradas de $-1 \pmod {13}$ son $5,8 \pmod {13}$ pero $154 \equiv 11 \pmod {13}.$
Las raíces cuadradas de $-1 \pmod {17}$ son $4,13 \pmod {17}$ pero $154 \equiv 1 \pmod {17}.$
Las raíces cuadradas de $-1 \pmod {29}$ son $12,17 \pmod {29}$ pero $154 \equiv 9 \pmod {29}.$
Las raíces cuadradas de $-1 \pmod {37}$ son $6,31 \pmod {37}.$ $$154 \equiv 6 \pmod {37}.$$
