Primos 4k+1 y residuos cuadráticos

Avatar de Usuario
AgusBarreto

OFO - Medalla de Bronce-OFO 2015 OFO - Medalla de Bronce-OFO 2016 OFO - Jurado-OFO 2017 FOFO 7 años - Jurado-FOFO 7 años OFO - Jurado-OFO 2018
FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022
Mensajes: 157
Registrado: Sab 15 Sep, 2012 6:28 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: San Martín, Buenos Aires

Primos 4k+1 y residuos cuadráticos

Mensaje sin leer por AgusBarreto »

En todo el post $p$ representa un número primo impar. Decimos que un entero $a$ es residuo cuadrático módulo $p$ si existe un entero $x$ tal que $x^2 \equiv a \pmod p$. Vamos a enunciar y demostrar tres lemas:

Lema 1: $-1$ es residuo cuadrático módulo $p$ si y sólo si $p \equiv 1 \pmod 4$
Spoiler: mostrar
Si $p \equiv 1 \pmod 4$ podemos usar Teorema de Wilson para construir un número cuyo cuadrado sea $-1 \pmod p$:

$-1\equiv(p-1)!\equiv 1\cdot\ldots\cdot \frac{p-1}{2}\frac{p+1}{2}\cdot\ldots\cdot(p-1)\equiv\left(\left(\frac{p-1}{2}\right)!\right)^2\cdot(-1)^{\frac{p-1}{2}}\equiv\left(\left(\frac{p-1}{2}\right)!\right)^2 \pmod p$

Esto gracias a que $\frac{p+1}{2}\cdot\ldots\cdot(p-1) \equiv (-\frac{p-1}{2})\cdot\ldots\cdot (-1) \pmod p$ y que $\frac{p-1}{2}$ es par.

Si $p \equiv 3 \pmod 4$, notamos que $x^4 \equiv (x^2)^2 \equiv 1 \pmod p$ y usamos Fermatito:

$1 \equiv x^{p-1} = x^{4k+2} = x^2x^{4k} \equiv -1\cdot(x^4)^k \equiv -1\cdot(1)^k \equiv-1\pmod{p}$
lo cual es absurdo ya que $p \neq 2$.
Lema 2: Si $a$ (coprimo con $p$) es residuo cuadrático módulo $p$, entonces es residuo cuadrático módulo $p^k$ para todo $k$ entero positivo.
Spoiler: mostrar
Vamos a probar que si $a$ es residuo cuadrático de $p^k$ entonces es residuo cuadrático de $p^{k+1}$:

Sabemos por lo supuesto que existe un entero $x$ tal que $x^2 \equiv a \pmod {p^k}$, entonces $x^2 = p^k \cdot m +a$ para algún entero $m$.
Ahora consideremos el entero $(x + p^k \cdot b)^2$ donde $b$ es un entero que podremos elegir a nuestra conveniencia y veremos debajo que existe un valor de $b$ tal que $(x + p^k \cdot b)^2 \equiv a \pmod {p^{k+1}}$. Expandiendo y teniendo en cuenta que $p^{2k} \equiv p^{k+1}p^{k-1} \equiv 0 \pmod {p^{k+1}}$ nos queda

$(x + p^k \cdot b)^2 \equiv x^2 + 2xp^kb + p^{2k}b^2 \equiv x^2 + 2xp^kb \equiv p^k \cdot m +a + 2xp^kb \equiv a + p^k(m+2xb) \pmod {p^{k+1}}$

Queremos que $m+2xb \equiv 0 \pmod p$ es decir un valor de $b$ y un entero $c$ tal que $m+2x \cdot b=p \cdot c$, o equivalentemente $m=p \cdot c - 2x \cdot b$. Como $2x$ y $p$ son coprimos, por la Identidad de Bézout existen tales valores de $b$ y $c$ y por lo tanto,

$(x + p^k \cdot b)^2 \equiv a + p^k (m + 2xb) \equiv a \pmod {p^{k+1}}$

Concluímos que $a$ es residuo cuadrático módulo $p^{k+1}$. Esto prueba, por inducción, que si $a$ es residuo cuadrático módulo $p$ entonces es residuo cuadrático módulo $p^k$ para todo $k$ entero positivo.
Lema 3: si $n$ es un entero positivo cuyos divisores primos son todos de la forma $4k+1$ con $k$ entero positivo, entonces $-1$ es residuo cuadrático módulo $n$.
Spoiler: mostrar
Sea $n=p_1^{\alpha_1}\cdot p_2^{\alpha_2} \ldots p_r^{\alpha_r}$ la factorización en primos de $n$. Por el Lema 2 tenemos que $-1$ es residuo cuadrático módulo $p_i^{\alpha_i}$ para todo $1\leq i \leq r$.
Existen entonces $x_1, \ldots, x_r$ tales que:
$x_1^2 \equiv -1 \pmod {p_1^{\alpha_1}}$
$\vdots$
$x_r^2 \equiv -1 \pmod {p_r^{\alpha_r}}$

Ahora, como todos los $p_i^{\alpha_i}$ son coprimos dos a dos, por Teorema Chino del Resto existe un único entero $x$ con $0 \leq x \leq p_1^{\alpha_1}\cdot p_2^{\alpha_2} \ldots p_r^{\alpha_r}=n$ tal que $x \equiv x_i \pmod {p_i^{\alpha_i}}$ para todo $1 \leq i \leq r$. Como $x$ es solución, debe ser $x^2 \equiv -1 \pmod {p_i^{\alpha_i}}$ para todo $1 \leq i \leq r$ y por lo tanto como $n= p_1^{\alpha_1}\cdot p_2^{\alpha_2} \ldots p_r^{\alpha_r}$, tenemos que $x^2 \equiv -1 \pmod n$, lo que nos dice que $-1$ es residuo cuadrático módulo $n$. Y con eso terminamos. ■
Última edición por AgusBarreto el Sab 29 Dic, 2018 5:02 am, editado 1 vez en total.
6  
Avatar de Usuario
BrunoDS

OFO - Medalla de Plata-OFO 2018 OFO - Medalla de Oro-OFO 2019
Mensajes: 99
Registrado: Dom 16 Nov, 2014 7:09 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Martínez

Re: Primos 4k+1 y residuos cuadráticos

Mensaje sin leer por BrunoDS »

Lema 3: si n es un entero positivo cuyos divisores primos son todos de la forma 4k+1 con k entero positivo, entonces −1 es residuo cuadrático módulo n.
Usando el Lema 1 nos dice que el Lema 3 es si y sólo si, no?
"No se olviden de entregar la prueba antes de irse..."
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Primos 4k+1 y residuos cuadráticos

Mensaje sin leer por Gianni De Rico »

Sí, porque si $-1$ es un residuo cuadrático módulo $n$, entonces es un residuo cuadrático módulo $p$ para todo $p$ primo tal que $p\mid n$, entonces por el Lema 1 tenemos que $p$ es de la forma $4k+1$
♪♫ do re mi función lineal ♪♫
Avatar de Usuario
BrunoDS

OFO - Medalla de Plata-OFO 2018 OFO - Medalla de Oro-OFO 2019
Mensajes: 99
Registrado: Dom 16 Nov, 2014 7:09 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Martínez

Re: Primos 4k+1 y residuos cuadráticos

Mensaje sin leer por BrunoDS »

Podemos además agregar al $2$ en el lema 1 y en la factorización del Lema 3, pero no a $2^x$ si $x\geq2$, ya que si miramos módulo $4$, sabemos que no existe un $a$ tal que $a² \equiv -1\pmod 4$
"No se olviden de entregar la prueba antes de irse..."
Responder