Supongamos que un primo $p$ divide a $n^2+1$, entonces es fácil ver que $ n$ y $p$ son primos relativos. Luego, por el PTF tenemos:
$\displaystyle n^{p-1} \equiv 1 \pmod{p}$ ... (1)
ahora, por hipótesis, sabemos que
$\displaystyle n^2 \equiv -1 \pmod{p}$
Elevemos esta igualdad a la $(p-1)/2$
$\displaystyle (n^2)^{(p-1)/2} \equiv (-1)^{(p-1)/2} \pmod{p}$ ... (2)
$\displaystyle n^{p-1} \equiv (-1)^{(p-1)/2} \pmod{p}$ ... (3)
Uniendo (1) y (3) llegamos a que:
$\displaystyle (-1)^{(p-1)/2} \equiv 1 \pmod{p}$...(4)
Recordemos que al elevar $-1$ a una potencia par nos da $ 1$ y una impar da $-1$. Como $-1$ y $ 1$ no son congruentes módulo $ p$ entonces se deberá tener que $(-1)^{(p-1)/2}$ debe ser $ 1$, esto es, $(p-1)/2$ deberá ser par. Pero que $(p-1)/2$ sea par significa que $\displaystyle p \equiv 1} \pmod{4}$.
Utilizando residuos
Utilizando residuos cuadráticos podemos llegar a conclusiones interesantes. No tengo la demostración del Teorema que utilizaré, pero seguiré intentando (hace mucho que lo vi).
El Símbolo de Legendre se define como
$\displaystyle \left(\frac{a}{p}\right) = \left\{\begin{array}{ll} 0 & \textrm{si }a|p \\ 1 & \textrm{si }a\textrm{ es residuo cuadratico modulo }p\\ -1 & \textrm{si }a\textrm{ es residuo no-cuadratico modulo }p\end{array} \right.$
Sabemos que $(-1,p)=1$ con $p$ primo, así que podemos utilizar el Criterio de Euler que dice
$\displaystyle a^{\frac{p-1}{2}}\equiv \left(\frac{a}{p}\right) \pmod{p}$
Si $p$ es un primo de la forma $4k+3$ tal que $p|n^2+1$, esto implica que -1 debe de ser residuo cuadrático módulo $p$, así que por la definición del símbolo de Legendre tenemos:
$\displaystyle \left( \frac{-1}{p} \right) = 1$ ... (1)
pero utilizando el Criterio de Euler tenemos:
$\displaystyle (-1)^{\frac{p-1}{2}} = (-1)^{\frac{4k+3-1}{2}}=(-1)^{2k+1} = -1 \equiv \left(\frac{-1}{p}\right) \pmod{p}$ ... (2)
Observando (1) y (2) llegamos a una contradicción. Esto quiere decir que -1 es residuo no-cuadrático bajo módulo $p$ cuando $p$ es un primo de la forma $4k+3$, así que si $p$ divide a $n^2+1$ entonces tiene que ser de la forma $4k+1$ (todos los primos impares se pueden escribir como $4k+1$ ó $4k+3$). Con esto termina la solución.
Creo que el símbolo de
Creo que el símbolo de Legendre y el criterio de Euler son resultado posteriores al ejercicio de esta sección. Me parece que lo más sano es demostrarlo sin el uso de éstos conceptos.
Como sugerencia, usa sólo el pequeño teorema de Fermat [1].
Este problema tiene como
Este problema tiene como consecuencia lo siguiente:
Consideremos un entero $ M$, tal que, tiene un factor primo $ p \equiv 3$ (mód 4). Entonces, $Mk - 1$ no es un cuadrado perfecto.
La razón de esto es que, de existir $ n$ tal que $n^2 = Mk -1$, se tendrá que $ M$ divide a $n^2 + 1$, en consecuencia, $ p$ divide a $n^2+1$. Y por el ejercicio, se deberá tener que $ p \equiv 1$ (mód 4), contradiciendo la hipótesis de que $ p$ satisfacía que $p \equiv 3$ (mód 4).
Un caso particula de esta observación general es el problema No es un cuadrado perfecto [2], propuesto por Fernando el 15 de Mayo. En el se pide demostrar que $187y-1$ no es un cuadrado perfecto.
Si, me fui muy al extremo.
Si, me fui muy al extremo. Hare otro intento usando la sugerencia que dice, lo acabo de pensar cuando fui a la tiendita.
Supongamos que un primo $p$ divide a $n^2+1$, entonces es facil ver que $ n$ y $p$ son primos relativos. Luego, por el PTF tenemos:
$\displaystyle n^{p-1} \equiv 1 \pmod{p}$ ... (1)
ahora, por hipotesis, sabemos que
$\displaystyle n^2 \equiv -1 \pmod{p}$
lo cual implica que
$\displaystyle n^{4m+2} \equiv -1 \pmod{p}$ ... (2)
$\displaystyle n^{4m} \equiv 1 \pmod{p}$ ... (3)
para algun entero $m$. Si (2) se cumple, entonces (1) no se cumple, y llegamos a una contradiccion. La unica posibilidad para que (1) se cumpla es que (3) se cumpla tambien (sin que (2) se cumpla), y para que (3) se cumpla tenemos que
$p-1 \equiv 0 \pmod{4}$
$p \equiv 1 \pmod{4}$
que es lo que queriamos probar.
Puse tu solución con algunas
Puse tu solución con algunas modificaciones que creo que la hacen más clara.
Saludos
Sí, queda más claro como lo
Sí, queda más claro como lo puso, gracias! :D! Es un problema muy interesante.