Lema de Gauss (teoría de números)

Condición bajo la cual un entero es un residuo cuadrático

El lema de Gauss en teoría de números establece una condición para que un número entero sea un residuo cuadrático . Aunque no es útil desde el punto de vista computacional, tiene importancia teórica, ya que se utiliza en algunas pruebas de reciprocidad cuadrática .

Hizo su primera aparición en la tercera prueba de reciprocidad cuadrática de Carl Friedrich Gauss (1808) ^{[1] : 458–462} y la demostró nuevamente en su quinta prueba (1818). ^{[1] : 496–501}

Enunciado del lema

Para cualquier primo impar p sea a un entero que es coprimo con p .

Consideremos los números enteros

${\displaystyle a,2a,3a,\dots ,{\frac {p-1}{2}}a}$

y sus residuos menos positivos módulo p . Estos residuos son todos distintos, por lo que hay ( p − 1)/2 de ellos.

Sea n el número de estos residuos que son mayores que p /2 . Entonces

${\displaystyle \left({\frac {a}{p}}\right)=(-1)^{n},}$

¿Dónde está el símbolo de Legendre ? ${\displaystyle \left({\frac {a}{p}}\right)}$

Ejemplo

Tomando p = 11 y a = 7, la secuencia relevante de números enteros es

7, 14, 21, 28, 35.

Después de la reducción módulo 11, esta secuencia se convierte en

7, 3, 10, 6, 2.

Tres de estos números enteros son mayores que 11/2 (es decir, 6, 7 y 10), por lo que n = 3. En consecuencia, el lema de Gauss predice que

${\displaystyle \left({\frac {7}{11}}\right)=(-1)^{3}=-1.}$

De hecho, esto es correcto, porque 7 no es un residuo cuadrático módulo 11.

La secuencia de residuos anterior

7, 3, 10, 6, 2

También puede escribirse

−4, 3, −1, −5, 2.

En esta forma, los números enteros mayores que 11/2 aparecen como números negativos. También es evidente que los valores absolutos de los residuos son una permutación de los residuos.

1, 2, 3, 4, 5.

Prueba

Una prueba bastante simple, ^{[1] : 458–462} que recuerda a una de las pruebas más simples del pequeño teorema de Fermat , se puede obtener evaluando el producto

${\displaystyle Z=a\cdot 2a\cdot 3a\cdot \cdots \cdot {\frac {p-1}{2}}a}$

módulo p de dos maneras diferentes. Por un lado es igual a

${\displaystyle Z=a^{(p-1)/2}\left(1\cdot 2\cdot 3\cdot \cdots \cdot {\frac {p-1}{2}}\right)}$

La segunda evaluación requiere más trabajo. Si x es un residuo distinto de cero módulo p , definamos el "valor absoluto" de x como

${\displaystyle |x|={\begin{cases}x&{\mbox{if }}1\leq x\leq {\frac {p-1}{2}},\\p-x&{\mbox{if }}{\frac {p+1}{2}}\leq x\leq p-1.\end{cases}}}$

Puesto que n cuenta aquellos múltiplos ka que están en el último rango, y puesto que para esos múltiplos, − ka está en el primer rango, tenemos

${\displaystyle Z=(-1)^{n}\left(|a|\cdot |2a|\cdot |3a|\cdot \cdots \cdots \left|{\frac {p-1}{2}}a\right|\right).}$

Ahora observe que los valores | ra | son distintos para r = 1, 2, …, ( p − 1)/2 . De hecho, tenemos

${\displaystyle {\begin{aligned}|ra|&\equiv |sa|&{\pmod {p}}\\ra&\equiv \pm sa&{\pmod {p}}\\r&\equiv \pm s&{\pmod {p}}\end{aligned}}}$

porque a es coprimo de p .

Esto da r = s , ya que r y s son residuos mínimos positivos. Pero hay exactamente ( p − 1)/2 de ellos, por lo que sus valores son un reordenamiento de los números enteros 1, 2, …, ( p − 1)/2 . Por lo tanto,

${\displaystyle Z=(-1)^{n}\left(1\cdot 2\cdot 3\cdot \cdots \cdot {\frac {p-1}{2}}\right).}$

En comparación con nuestra primera evaluación, podemos cancelar el factor distinto de cero.

${\displaystyle 1\cdot 2\cdot 3\cdot \cdots \cdot {\frac {p-1}{2}}}$

y nos quedamos con

${\displaystyle a^{(p-1)/2}=(-1)^{n}.}$

Este es el resultado deseado, porque según el criterio de Euler el lado izquierdo es simplemente una expresión alternativa para el símbolo de Legendre . ${\displaystyle \left({\frac {a}{p}}\right)}$

Generalización

Para cualquier primo impar p sea a un entero que es coprimo con p .

Sea un conjunto tal que es la unión disjunta de y . ${\displaystyle I\subset (\mathbb {Z} /p\mathbb {Z} )^{\times }}$ ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }}$ ${\displaystyle I}$ ${\displaystyle -I=\{-i:i\in I\}}$

Entonces , donde . ^[2] ${\displaystyle \left({\frac {a}{p}}\right)=(-1)^{t}}$ ${\displaystyle t=\#\{j\in I:aj\in -I\}}$

En la declaración original, . ${\displaystyle I=\{1,2,\dots ,{\frac {p-1}{2}}\}}$

La prueba es casi la misma.

Aplicaciones

El lema de Gauss se utiliza en muchas, ^{[3] : Cap. 1  [3] : 9} pero de ninguna manera en todas, las pruebas conocidas de reciprocidad cuadrática.

Por ejemplo, Gotthold Eisenstein ^{[3] : 236} utilizó el lema de Gauss para demostrar que si p es un primo impar entonces

${\displaystyle \left({\frac {a}{p}}\right)=\prod _{n=1}^{(p-1)/2}{\frac {\sin {(2\pi an/p)}}{\sin {(2\pi n/p)}}},}$

y utilizó esta fórmula para demostrar la reciprocidad cuadrática. Al utilizar funciones elípticas en lugar de circulares , demostró las leyes de reciprocidad cúbica y cuártica . ^{[3] : Cap. 8}

Leopold Kronecker ^{[3] : En el ejemplo 1.34} se utilizó el lema para demostrar que

${\displaystyle \left({\frac {p}{q}}\right)=\operatorname {sgn} \prod _{i=1}^{\frac {q-1}{2}}\prod _{k=1}^{\frac {p-1}{2}}\left({\frac {k}{p}}-{\frac {i}{q}}\right).}$

Al cambiar p y q se obtiene inmediatamente reciprocidad cuadrática.

También se utiliza en lo que probablemente sean las pruebas más simples de la "segunda ley suplementaria".

${\displaystyle \left({\frac {2}{p}}\right)=(-1)^{(p^{2}-1)/8}={\begin{cases}+1{\text{ if }}p\equiv \pm 1{\pmod {8}}\\-1{\text{ if }}p\equiv \pm 3{\pmod {8}}\end{cases}}}$

Poderes superiores

Las generalizaciones del lema de Gauss se pueden utilizar para calcular símbolos de residuos de mayor potencia. En su segunda monografía sobre reciprocidad bicuadrática, ^{[4] : §§69–71} Gauss utilizó un lema de cuarta potencia para derivar la fórmula para el carácter bicuadrático de 1 + i en Z [ i ] , el anillo de los números enteros gaussianos . Posteriormente, Eisenstein utilizó versiones de tercera y cuarta potencia para demostrar la reciprocidad cúbica y cuártica . ^{[3] : Cap. 8}

norteEl símbolo del residuo de potencia

Sea k un cuerpo de números algebraicos con anillo de números enteros y sea un ideal primo . La norma ideal de se define como la cardinalidad del anillo de clases de residuos. Como es primo, este es un cuerpo finito , por lo que la norma ideal es . ${\displaystyle {\mathcal {O}}_{k},}$ ${\displaystyle {\mathfrak {p}}\subset {\mathcal {O}}_{k}}$ ${\displaystyle \mathrm {N} {\mathfrak {p}}}$ ${\displaystyle {\mathfrak {p}}}$ ${\displaystyle {\mathfrak {p}}}$ ${\displaystyle {\mathcal {O}}_{k}/{\mathfrak {p}}}$ ${\displaystyle \mathrm {N} {\mathfrak {p}}=|{\mathcal {O}}_{k}/{\mathfrak {p}}|}$

Supongamos que hay una raíz n- ésima primitiva de la unidad y que n y son coprimos (es decir, ). Entonces no pueden existir dos raíces n- ésimas distintas de la unidad congruentes módulo . ${\displaystyle \zeta _{n}\in {\mathcal {O}}_{k},}$ ${\displaystyle {\mathfrak {p}}}$ ${\displaystyle n\not \in {\mathfrak {p}}}$ ${\displaystyle {\mathfrak {p}}}$

Esto se puede demostrar por contradicción, empezando por suponer que mod , 0 < r < s ≤ n . Sea t = s − r tal que mod , y 0 < t < n . A partir de la definición de raíces de la unidad, ${\displaystyle \zeta _{n}^{r}\equiv \zeta _{n}^{s}}$ ${\displaystyle {\mathfrak {p}}}$ ${\displaystyle \zeta _{n}^{t}\equiv 1}$ ${\displaystyle {\mathfrak {p}}}$

${\displaystyle x^{n}-1=(x-1)(x-\zeta _{n})(x-\zeta _{n}^{2})\dots (x-\zeta _{n}^{n-1}),}$

y dividiendo por x − 1 da

${\displaystyle x^{n-1}+x^{n-2}+\dots +x+1=(x-\zeta _{n})(x-\zeta _{n}^{2})\dots (x-\zeta _{n}^{n-1}).}$

Dejando x = 1 y tomando residuos mod , ${\displaystyle {\mathfrak {p}}}$

${\displaystyle n\equiv (1-\zeta _{n})(1-\zeta _{n}^{2})\dots (1-\zeta _{n}^{n-1}){\pmod {\mathfrak {p}}}.}$

Como n y son coprimos, mod pero bajo el supuesto, uno de los factores de la derecha debe ser cero. Por lo tanto, el supuesto de que dos raíces distintas son congruentes es falso. ${\displaystyle {\mathfrak {p}}}$ ${\displaystyle n\not \equiv 0}$ ${\displaystyle {\mathfrak {p}},}$

Por lo tanto, las clases de residuos de que contienen las potencias de ζ _n son un subgrupo de orden n de su grupo (multiplicativo) de unidades. Por lo tanto, el orden de es un múltiplo de n , y ${\displaystyle {\mathcal {O}}_{k}/{\mathfrak {p}}}$ ${\displaystyle ({\mathcal {O}}_{k}/{\mathfrak {p}})^{\times }={\mathcal {O}}_{k}/{\mathfrak {p}}-\{0\}.}$ ${\displaystyle ({\mathcal {O}}_{k}/{\mathfrak {p}})^{\times }}$

${\displaystyle {\begin{aligned}\mathrm {N} {\mathfrak {p}}&=|{\mathcal {O}}_{k}/{\mathfrak {p}}|\\&=\left|({\mathcal {O}}_{k}/{\mathfrak {p}})^{\times }\right|+1\\&\equiv 1{\pmod {n}}.\end{aligned}}}$

Existe un análogo del teorema de Fermat en . Si para , entonces ^{[3] : Cap. 4.1} ${\displaystyle {\mathcal {O}}_{k}}$ ${\displaystyle \alpha \in {\mathcal {O}}_{k}}$ ${\displaystyle \alpha \not \in {\mathfrak {p}}}$

${\displaystyle \alpha ^{\mathrm {N} {\mathfrak {p}}-1}\equiv 1{\pmod {\mathfrak {p}}},}$

y como mod n , ${\displaystyle \mathrm {N} {\mathfrak {p}}\equiv 1}$

${\displaystyle \alpha ^{\frac {\mathrm {N} {\mathfrak {p}}-1}{n}}\equiv \zeta _{n}^{s}{\pmod {\mathfrak {p}}}}$

está bien definida y es congruente con una única raíz n- ésima de la unidad ζ _n ^s .

Esta raíz de la unidad se llama símbolo de residuo de potencia n y ${\displaystyle {\mathcal {O}}_{k},}$ se denota por

${\displaystyle {\begin{aligned}\left({\frac {\alpha }{\mathfrak {p}}}\right)_{n}&=\zeta _{n}^{s}\\&\equiv \alpha ^{\frac {\mathrm {N} {\mathfrak {p}}-1}{n}}{\pmod {\mathfrak {p}}}.\end{aligned}}}$

Se puede demostrar que ^{[3] : Prop. 4.1}

${\displaystyle \left({\frac {\alpha }{\mathfrak {p}}}\right)_{n}=1}$

si y sólo si existe un tal que α ≡ η ⁿ mod . ${\displaystyle \eta \in {\mathcal {O}}_{k}}$ ${\displaystyle {\mathfrak {p}}}$

1/nortesistemas

Sea el grupo multiplicativo de las raíces n -ésimas de la unidad, y sean representantes de las clases laterales de Entonces A se llama un sistema 1/ n mod ^{[3] : Cap. 4.2} ${\displaystyle \mu _{n}=\{1,\zeta _{n},\zeta _{n}^{2},\dots ,\zeta _{n}^{n-1}\}}$ ${\displaystyle A=\{a_{1},a_{2},\dots ,a_{m}\}}$ ${\displaystyle ({\mathcal {O}}_{k}/{\mathfrak {p}})^{\times }/\mu _{n}.}$ ${\displaystyle {\mathfrak {p}}.}$

En otras palabras, hay números en el conjunto y este conjunto constituye un conjunto representativo para ${\displaystyle mn=\mathrm {N} {\mathfrak {p}}-1}$ ${\displaystyle A\mu =\{a_{i}\zeta _{n}^{j}\;:\;1\leq i\leq m,\;\;\;0\leq j\leq n-1\},}$ ${\displaystyle ({\mathcal {O}}_{k}/{\mathfrak {p}})^{\times }.}$

Los números 1, 2, … ( p − 1)/2 , utilizados en la versión original del lema, son un sistema 1/2 (mod p ).

Construir un sistema 1/ n es sencillo: sea M un conjunto representativo de Elija cualquiera y elimine los números congruentes con de M . Elija un ₂ de M y elimine los números congruentes con Repita hasta que se agote M. Entonces { a ₁ , a ₂ , … a _m } es un sistema 1/ n mod ${\displaystyle ({\mathcal {O}}_{k}/{\mathfrak {p}})^{\times }.}$ ${\displaystyle a_{1}\in M}$ ${\displaystyle a_{1},a_{1}\zeta _{n},a_{1}\zeta _{n}^{2},\dots ,a_{1}\zeta _{n}^{n-1}}$ ${\displaystyle a_{2},a_{2}\zeta _{n},a_{2}\zeta _{n}^{2},\dots ,a_{2}\zeta _{n}^{n-1}}$ ${\displaystyle {\mathfrak {p}}.}$

El lema paranortelos poderes

El lema de Gauss puede extenderse al símbolo del residuo de potencia n de la siguiente manera. ^{[3] : Prop. 4.3} Sea una raíz n primitiva de la unidad, un ideal primo (es decir , es coprimo tanto con γ como con n ) y sea A = { a ₁ , a ₂ , …, a _m } un sistema 1/ n mod ${\displaystyle \zeta _{n}\in {\mathcal {O}}_{k}}$ ${\displaystyle {\mathfrak {p}}\subset {\mathcal {O}}_{k}}$ ${\displaystyle \gamma \in {\mathcal {O}}_{k},\;\;n\gamma \not \in {\mathfrak {p}},}$ ${\displaystyle {\mathfrak {p}}}$ ${\displaystyle {\mathfrak {p}}.}$

Entonces, para cada i , 1 ≤ i ≤ m , existen enteros π ( i ) , únicos (mod m ), y b ( i ) , únicos (mod n ), tales que

${\displaystyle \gamma a_{i}\equiv \zeta _{n}^{b(i)}a_{\pi (i)}{\pmod {\mathfrak {p}}},}$

y el símbolo del residuo de potencia n está dado por la fórmula

${\displaystyle \left({\frac {\gamma }{\mathfrak {p}}}\right)_{n}=\zeta _{n}^{b(1)+b(2)+\dots +b(m)}.}$

El lema clásico para el símbolo de Legendre cuadrático es el caso especial n = 2 , ζ ₂ = −1 , A = {1, 2, …, ( p − 1)/2} , b ( k ) = 1 si ak > p /2 , b ( k ) = 0 si ak < p /2 .

Prueba

La prueba del lema de la n -ésima potencia utiliza las mismas ideas que se usaron en la prueba del lema cuadrático.

La existencia de los números enteros π ( i ) y b ( i ) , y su unicidad (mod m ) y (mod n ), respectivamente, provienen del hecho de que Aμ es un conjunto representativo.

Supongamos que π ( i ) = π ( j ) = p , es decir

${\displaystyle \gamma a_{i}\equiv \zeta _{n}^{r}a_{p}{\pmod {\mathfrak {p}}}}$

y

${\displaystyle \gamma a_{j}\equiv \zeta _{n}^{s}a_{p}{\pmod {\mathfrak {p}}}.}$

Entonces

${\displaystyle \zeta _{n}^{s-r}\gamma a_{i}\equiv \zeta _{n}^{s}a_{p}\equiv \gamma a_{j}{\pmod {\mathfrak {p}}}}$

Como γ y son coprimos, ambos lados se pueden dividir por γ , lo que da ${\displaystyle {\mathfrak {p}}}$

${\displaystyle \zeta _{n}^{s-r}a_{i}\equiv a_{j}{\pmod {\mathfrak {p}}},}$

lo cual, dado que A es un sistema 1/ n , implica s = r e i = j , mostrando que π es una permutación del conjunto {1, 2, …, m } .

Entonces, por un lado, por la definición del símbolo de residuo de potencia,

${\displaystyle {\begin{aligned}(\gamma a_{1})(\gamma a_{2})\dots (\gamma a_{m})&=\gamma ^{\frac {\mathrm {N} {\mathfrak {p}}-1}{n}}a_{1}a_{2}\dots a_{m}\\&\equiv \left({\frac {\gamma }{\mathfrak {p}}}\right)_{n}a_{1}a_{2}\dots a_{m}{\pmod {\mathfrak {p}}},\end{aligned}}}$

y por otro lado, como π es una permutación,

${\displaystyle {\begin{aligned}(\gamma a_{1})(\gamma a_{2})\dots (\gamma a_{m})&\equiv {\zeta _{n}^{b(1)}a_{\pi (1)}}{\zeta _{n}^{b(2)}a_{\pi (2)}}\dots {\zeta _{n}^{b(m)}a_{\pi (m)}}&{\pmod {\mathfrak {p}}}\\&\equiv \zeta _{n}^{b(1)+b(2)+\dots +b(m)}a_{\pi (1)}a_{\pi (2)}\dots a_{\pi (m)}&{\pmod {\mathfrak {p}}}\\&\equiv \zeta _{n}^{b(1)+b(2)+\dots +b(m)}a_{1}a_{2}\dots a_{m}&{\pmod {\mathfrak {p}}},\end{aligned}}}$

entonces

${\displaystyle \left({\frac {\gamma }{\mathfrak {p}}}\right)_{n}a_{1}a_{2}\dots a_{m}\equiv \zeta _{n}^{b(1)+b(2)+\dots +b(m)}a_{1}a_{2}\dots a_{m}{\pmod {\mathfrak {p}}},}$

y como para todo 1 ≤ i ≤ m , a _i y son coprimos, a ₁ a ₂ … a _m se pueden cancelar desde ambos lados de la congruencia, ${\displaystyle {\mathfrak {p}}}$

${\displaystyle \left({\frac {\gamma }{\mathfrak {p}}}\right)_{n}\equiv \zeta _{n}^{b(1)+b(2)+\dots +b(m)}{\pmod {\mathfrak {p}}},}$

y el teorema se deduce del hecho de que no pueden existir dos raíces n- ésimas distintas de la unidad congruentes (mod ). ${\displaystyle {\mathfrak {p}}}$

Relación con la transferencia en la teoría de grupos

Sea G el grupo multiplicativo de clases de residuos distintos de cero en Z / p Z , y sea H el subgrupo {+1, −1}. Consideremos los siguientes representantes de clases laterales de H en G ,

${\displaystyle 1,2,3,\dots ,{\frac {p-1}{2}}.}$

Aplicando la maquinaria de transferencia a esta colección de representantes de clases laterales, obtenemos el homomorfismo de transferencia

${\displaystyle \phi :G\to H,}$

que resulta ser la función que envía a a (−1) ⁿ , donde a y n son como en el enunciado del lema. El lema de Gauss puede entonces verse como un cálculo que identifica explícitamente este homomorfismo como el carácter de residuo cuadrático.

Véase también

• Lema de Zolotarev

Referencias

1. Gauss, Carl Friedrich (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae y otros artículos sobre teoría de números) (en alemán), traducido por H. Maser (2ª ed.), Nueva York: Chelsea, ISBN 0-8284-0191-8
2. Kremnizer, Kobi. Lecciones de teoría de números 2022 (PDF) .
3. Lemmermeyer, Franz (2000), Leyes de reciprocidad: de Euler a Eisenstein , Berlín: Springer , ISBN 3-540-66957-4
4. Gauss, Carl Friedrich (1832), Theoria residuorum biquadraticorum, Commentatio secunda , vol. 7, Gotinga: comentario. Soc. ciencia regia