Símbolo de Legendre
Función en la teoría de números
Símbolo de Legendre ( ⁠a/pag)
para varios a (en la parte superior) y p (en el lado izquierdo).
a
pag
012345678910
301-1
501-1-11
7011-11-1-1
11- 0− 1-11− 11-1-1-1− 1-1

Sólo se muestran 0 ≤ a < p , ya que debido a la primera propiedad que se muestra a continuación, cualquier otro a puede reducirse módulo p . Los residuos cuadráticos están resaltados en amarillo y corresponden precisamente a los valores 0 y 1.

En teoría de números , el símbolo de Legendre es una función multiplicativa con valores 1, −1, 0 que es un carácter cuadrático módulo de un número primo impar p : su valor en un residuo cuadrático (distinto de cero) módulo  p es 1 y en un residuo no cuadrático ( no residuo ) es −1. Su valor en cero es 0.

El símbolo de Legendre fue introducido por Adrien-Marie Legendre en 1798 [1] en el curso de sus intentos de demostrar la ley de reciprocidad cuadrática . Las generalizaciones del símbolo incluyen el símbolo de Jacobi y los caracteres de Dirichlet de orden superior. La conveniencia de notación del símbolo de Legendre inspiró la introducción de varios otros "símbolos" utilizados en la teoría de números algebraicos , como el símbolo de Hilbert y el símbolo de Artin .

Definición

Sea un número primo impar . Un entero es un residuo cuadrático módulo si es congruente con un cuadrado perfecto módulo y es un no residuo cuadrático módulo en caso contrario. El símbolo de Legendre es una función de y se define como pag {\estilo de visualización p} a {\estilo de visualización a} pag {\estilo de visualización p} pag {\estilo de visualización p} pag {\estilo de visualización p} a {\estilo de visualización a} pag {\estilo de visualización p}

( a pag ) = { 1 si  a  es un residuo cuadrático módulo  pag  y  a ≢ 0 ( modificación pag ) , − 1 si  a  es un módulo no residuo cuadrático  pag , 0 si  a ≡ 0 ( modificación pag ) . {\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}1&{\text{si }}a{\text{ es un residuo cuadrático módulo }}p{\text{ y }}a\not \equiv 0{\pmod {p}},\\-1&{\text{si }}a{\text{ es un no residuo cuadrático módulo }}p,\\0&{\text{si }}a\equiv 0{\pmod {p}}.\end{cases}}}

La definición original de Legendre fue mediante la fórmula explícita

( a pag ) ≡ a pag − 1 2 ( modificación pag )  y  ( a pag ) ∈ { − 1 , 0 , 1 } . {\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}\quad {\text{ y }}\quad \left({\frac {a}{p}}\right)\in \{-1,0,1\}.}

Según el criterio de Euler , que se había descubierto antes y era conocido por Legendre, estas dos definiciones son equivalentes. [2] Por lo tanto, la contribución de Legendre consistió en introducir una notación conveniente que registraba la residuosidad cuadrática de un  módulo  p . Para fines de comparación, Gauss utilizó la notación a R p , a N p según si a es un residuo o un no residuo módulo p . Por conveniencia tipográfica, el símbolo de Legendre a veces se escribe como ( a  |  p ) o ( a / p ). Para p fijo , la secuencia es periódica con período p y a veces se denomina secuencia de Legendre . Cada fila de la siguiente tabla muestra periodicidad, tal como se describe. ( 0 pag ) , ( 1 pag ) , ( 2 pag ) , … {\displaystyle \left({\tfrac {0}{p}}\right),\left({\tfrac {1}{p}}\right),\left({\tfrac {2}{p}}\right),\ldots }

Tabla de valores

La siguiente es una tabla de valores del símbolo de Legendre con p  ≤ 127, a  ≤ 30, p primo impar. ( a pag ) {\displaystyle \left({\frac {a}{p}}\right)}

a
pag
123456789101112131415161718192021222324252627282930
3− 1-10− 1-101-1- 01-101-10− 1-101-101-10− 1-101-10
51-1-1101-1-1101-1-1101-1-1101-1-1101-1-110
711-11-1-1011-11-1-1011-11-1-1011-11-1-1011
111-1111-1-1-11-101-1111-1-1-11-101-1111-1-1-1
131-111-1-1-1-111-1101-111-1-1-1-111-1101-111
1711-11-1-1-111-1-1-11-111011-11-1-1-111-1-1-11
191-1-11111-11-11-1-1-1-111-101-1-11111-11-11
231111-11-111-1-111-1-11-11-1-1-1-101111-11-1
291-1-11111-11-1-1-11-1-11-1-1-11-11111-1-1101
3111-111-11111-1-1-11-11-1111-1-1-1-11-1-11-1-1
371-111-1-11-11111-1-1-11-1-1-1-11-1-1-11111-11
4111-111-1-1111-1-1-1-1-11-11-111-11-11-1-1-1-1-1
431-1-11-11-1-1111-111111-1-1-11-1111-1-1-1-1-1
471111-11111-1-11-11-1111-1-11-1-111-111-1-1
531-1-11-111-1111-11-1111-1-1-1-1-1-111-1-111-1
591-1111-11-11-1-11-1-1111-11111-1-111111-1
611-1111-1-1-11-1-111111-1-111-11-1-11-11-1-1-1
671-1-11-11-1-111-1-1-11111-11-1111111-1-11-1
71111111-1111-11-1-111-1111-1-1-111-11-111
731111-11-111-1-11-1-1-11-111-1-1-1111-11-1-1-1
7911-111-1-11111-11-1-11-1111111-111-1-1-1-1
831-111-1-11-11111-1-1-111-1-1-11-11-1111111
8911-111-1-11111-1-1-1-1111-1111-1-11-1-1-1-1-1
971111-11-111-111-1-1-11-11-1-1-11-111-11-1-1-1
1011-1-1111-1-11-1-1-111-111-11111111-1-1-1-11
10311-11-1-1111-1-1-11111111-1-1-11-111-1111
1071-111-1-1-1-1111111-11-1-11-1-1-11-11-11-111
1091-1111-11-11-1-11-1-111-1-1-1111-1-111111-1
11311-11-1-1111-11-11111-11-1-1-11-1-111-11-11
12711-11-1-1-111-11-11-111111-111-1-111-1-1-11

Propiedades del símbolo de Legendre

Hay una serie de propiedades útiles del símbolo de Legendre que, junto con la ley de reciprocidad cuadrática , pueden utilizarse para calcularlo de manera eficiente.

  • Dado un generador , si , entonces es un residuo cuadrático si y solo si es par. Esto demuestra que la mitad de los elementos en son residuos cuadráticos. gramo ∈ F pag ∗ {\displaystyle g\in \mathbb {F} _{p}^{*}} incógnita = gramo a {\displaystyle x=g^{r}} incógnita {\estilo de visualización x} a {\estilo de visualización r} F pag ∗ {\displaystyle \mathbb {F}_{p}^{*}}
  • Si entonces el hecho de que pag ≡ 3  modificación  4 {\displaystyle p\equiv 3{\text{mod}}4}
    pag + 1 4 + pag + 1 4 = pag + 1 2 = ( pag − 1 ) + 2 2 = pag − 1 2 + 1 {\displaystyle {\frac {p+1}{4}}+{\frac {p+1}{4}}={\frac {p+1}{2}}={\frac {(p-1 )+2}{2}}={\frac {p-1}{2}}+1} nos da que es una raíz cuadrada del residuo cuadrático . a = incógnita ( pag + 1 ) / 4 {\displaystyle a=x^{(p+1)/4}} incógnita {\estilo de visualización x}
  • El símbolo de Legendre es periódico en su primer argumento (o superior): si a ≡ b (mod p ), entonces
    ( a pag ) = ( b pag ) . {\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right).}
  • El símbolo de Legendre es una función completamente multiplicativa de su argumento superior:
    ( a b pag ) = ( a pag ) ( b pag ) . {\displaystyle \left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right).}
  • En particular, el producto de dos números que son residuos cuadráticos o no residuos cuadráticos módulo p es un residuo, mientras que el producto de un residuo con un no residuo es un no residuo. Un caso especial es el símbolo de Legendre de un cuadrado:
    ( incógnita 2 pag ) = { 1 si  pag ∤ incógnita 0 si  pag ∣ incógnita . {\displaystyle \left({\frac {x^{2}}{p}}\right)={\begin{cases}1&{\mbox{si }}p\nmid x\\0&{\mbox{si }}p\mid x.\end{cases}}}
  • Cuando se lo considera como una función de a , el símbolo de Legendre es el único carácter de Dirichlet cuadrático (o de orden 2) módulo p . ( a pag ) {\displaystyle \left({\frac {a}{p}}\right)}
  • El primer suplemento a la ley de reciprocidad cuadrática:
    ( − 1 pag ) = ( − 1 ) pag − 1 2 = { 1  si  pag ≡ 1 ( modificación 4 ) − 1  si  pag ≡ 3 ( modificación 4 ) . {\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}1&{\mbox{ si }}p\equiv 1{\pmod {4}}\\-1&{\mbox{ si }}p\equiv 3{\pmod {4}}.\end{cases}}}
  • El segundo suplemento a la ley de reciprocidad cuadrática:
    ( 2 pag ) = ( − 1 ) pag 2 − 1 8 = { 1  si  pag ≡ 1  o  7 ( modificación 8 ) − 1  si  pag ≡ 3  o  5 ( modificación 8 ) . {\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\tfrac {p^{2}-1}{8}}={\begin{cases}1&{\mbox{ si }}p\equiv 1{\mbox{ o }}7{\pmod {8}}\\-1&{\mbox{ si }}p\equiv 3{\mbox{ o }}5{\pmod {8}}.\end{cases}}}
  • Fórmulas especiales para el símbolo de Legendre para valores pequeños de a : ( a pag ) {\displaystyle \left({\frac {a}{p}}\right)}
    • Para un primo impar p  ≠ 3,
      ( 3 pag ) = ( − 1 ) ⌊ pag + 1 6 ⌋ = { 1  si  pag ≡ 1  o  11 ( modificación 12 ) − 1  si  pag ≡ 5  o  7 ( modificación 12 ) . {\displaystyle \left({\frac {3}{p}}\right)=(-1)^{{\big \lfloor }{\frac {p+1}{6}}{\big \rfloor }}={\begin{cases}1&{\mbox{ if }}p\equiv 1{\mbox{ or }}11{\pmod {12}}\\-1&{\mbox{ if }}p\equiv 5{\mbox{ or }}7{\pmod {12}}.\end{cases}}}
    • Para un primo impar p  ≠ 5,
      ( 5 p ) = ( − 1 ) ⌊ 2 p + 2 5 ⌋ = { 1  if  p ≡ 1  or  4 ( mod 5 ) − 1  if  p ≡ 2  or  3 ( mod 5 ) . {\displaystyle \left({\frac {5}{p}}\right)=(-1)^{{\big \lfloor }{\frac {2p+2}{5}}{\big \rfloor }}={\begin{cases}1&{\mbox{ if }}p\equiv 1{\mbox{ or }}4{\pmod {5}}\\-1&{\mbox{ if }}p\equiv 2{\mbox{ or }}3{\pmod {5}}.\end{cases}}}
  • Los números de Fibonacci 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... se definen por la recurrencia F 1 = F 2 = 1, F n +1 = F n + F n −1 . Si p es un número primo entonces
    F p − ( p 5 ) ≡ 0 ( mod p ) , F p ≡ ( p 5 ) ( mod p ) . {\displaystyle F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p}},\qquad F_{p}\equiv \left({\frac {p}{5}}\right){\pmod {p}}.}
Por ejemplo,
( 2 5 ) = − 1 , F 3 = 2 , F 2 = 1 , ( 3 5 ) = − 1 , F 4 = 3 , F 3 = 2 , ( 5 5 ) = 0 , F 5 = 5 , ( 7 5 ) = − 1 , F 8 = 21 , F 7 = 13 , ( 11 5 ) = 1 , F 10 = 55 , F 11 = 89. {\displaystyle {\begin{aligned}\left({\tfrac {2}{5}}\right)&=-1,&F_{3}&=2,&F_{2}&=1,\\\left({\tfrac {3}{5}}\right)&=-1,&F_{4}&=3,&F_{3}&=2,\\\left({\tfrac {5}{5}}\right)&=0,&F_{5}&=5,&&\\\left({\tfrac {7}{5}}\right)&=-1,&F_{8}&=21,&F_{7}&=13,\\\left({\tfrac {11}{5}}\right)&=1,&F_{10}&=55,&F_{11}&=89.\end{aligned}}}

Símbolo de Legendre y reciprocidad cuadrática

Sean p y q primos impares distintos. Utilizando el símbolo de Legendre, la ley de reciprocidad cuadrática se puede enunciar de forma concisa:

( q p ) ( p q ) = ( − 1 ) p − 1 2 ⋅ q − 1 2 . {\displaystyle \left({\frac {q}{p}}\right)\left({\frac {p}{q}}\right)=(-1)^{{\tfrac {p-1}{2}}\cdot {\tfrac {q-1}{2}}}.}

Muchas pruebas de reciprocidad cuadrática se basan en el criterio de Euler.

( a p ) ≡ a p − 1 2 ( mod p ) . {\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\tfrac {p-1}{2}}{\pmod {p}}.}

Además, se idearon varias expresiones alternativas para el símbolo de Legendre con el fin de producir diversas pruebas de la ley de reciprocidad cuadrática.

∑ k = 0 p − 1 ζ a k 2 = ( a p ) ∑ k = 0 p − 1 ζ k 2 , ζ = e 2 π i p {\displaystyle \sum _{k=0}^{p-1}\zeta ^{ak^{2}}=\left({\frac {a}{p}}\right)\sum _{k=0}^{p-1}\zeta ^{k^{2}},\qquad \zeta =e^{\frac {2\pi i}{p}}}
en su cuarta [4] y sexta [5] pruebas de reciprocidad cuadrática.
( p q ) = sgn ⁡ ( ∏ i = 1 q − 1 2 ∏ k = 1 p − 1 2 ( k p − i q ) ) . {\displaystyle \left({\frac {p}{q}}\right)=\operatorname {sgn} \left(\prod _{i=1}^{\frac {q-1}{2}}\prod _{k=1}^{\frac {p-1}{2}}\left({\frac {k}{p}}-{\frac {i}{q}}\right)\right).}
Invirtiendo los roles de p y q , obtiene la relación entre ( ⁠pag/q⁠ ) ​​y ( ⁠q/pag⁠ ).
  • Una de las pruebas de Eisenstein [7] comienza mostrando que
( q p ) = ∏ n = 1 p − 1 2 sin ⁡ ( 2 π q n p ) sin ⁡ ( 2 π n p ) . {\displaystyle \left({\frac {q}{p}}\right)=\prod _{n=1}^{\frac {p-1}{2}}{\frac {\sin \left({\frac {2\pi qn}{p}}\right)}{\sin \left({\frac {2\pi n}{p}}\right)}}.}
Utilizando ciertas funciones elípticas en lugar de la función seno , Eisenstein pudo demostrar también la reciprocidad cúbica y cuártica .
  • El símbolo de Jacobi ( ⁠a/norte) es una generalización del símbolo de Legendre que permite un segundo argumento compuesto (inferior) n , aunque n debe seguir siendo impar y positivo. Esta generalización proporciona una forma eficiente de calcular todos los símbolos de Legendre sin realizar factorización en el proceso.
  • Una extensión adicional es el símbolo de Kronecker , en el que el argumento inferior puede ser cualquier número entero.
  • El símbolo del residuo de energía ( ⁠a/norte⁠ ) ​​n generaliza el símbolo de Legendre a una potencia n mayor . El símbolo de Legendre representa el símbolo de residuo de potencia para n  = 2.

Ejemplo computacional

Las propiedades anteriores, incluida la ley de reciprocidad cuadrática, se pueden utilizar para evaluar cualquier símbolo de Legendre. Por ejemplo:

( 12345 331 ) = ( 3 331 ) ( 5 331 ) ( 823 331 ) = ( 3 331 ) ( 5 331 ) ( 161 331 ) = ( 3 331 ) ( 5 331 ) ( 7 331 ) ( 23 331 ) = ( − 1 ) ( 331 3 ) ( 331 5 ) ( − 1 ) ( 331 7 ) ( − 1 ) ( 331 23 ) = − ( 1 3 ) ( 1 5 ) ( 2 7 ) ( 9 23 ) = − ( 1 3 ) ( 1 5 ) ( 2 7 ) ( 3 2 23 ) = − ( 1 ) ( 1 ) ( 1 ) ( 1 ) = − 1. {\displaystyle {\begin{aligned}\left({\frac {12345}{331}}\right)&=\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {823}{331}}\right)\\&=\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {161}{331}}\right)\\&=\left({\frac {3}{331}}\right)\left({\frac {5}{331}}\right)\left({\frac {7}{331}}\right)\left({\frac {23}{331}}\right)\\&=(-1)\left({\frac {331}{3}}\right)\left({\frac {331}{5}}\right)(-1)\left({\frac {331}{7}}\right)(-1)\left({\frac {331}{23}}\right)\\&=-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {9}{23}}\right)\\&=-\left({\frac {1}{3}}\right)\left({\frac {1}{5}}\right)\left({\frac {2}{7}}\right)\left({\frac {3^{2}}{23}}\right)\\&=-(1)(1)(1)(1)\\&=-1.\end{aligned}}}

O utilizando un cálculo más eficiente:

( 12345 331 ) = ( 98 331 ) = ( 2 ⋅ 7 2 331 ) = ( 2 331 ) = ( − 1 ) 331 2 − 1 8 = − 1. {\displaystyle \left({\frac {12345}{331}}\right)=\left({\frac {98}{331}}\right)=\left({\frac {2\cdot 7^{2}}{331}}\right)=\left({\frac {2}{331}}\right)=(-1)^{\tfrac {331^{2}-1}{8}}=-1.}

El artículo Símbolo de Jacobi tiene más ejemplos de manipulación del símbolo de Legendre.

Dado que no se conoce ningún algoritmo de factorización eficiente , pero sí algoritmos de exponenciación modular eficientes , en general es más eficiente utilizar la definición original de Legendre, por ejemplo

( 98 331 ) ≡ 98 331 − 1 2 ( mod 331 ) ≡ 98 165 ( mod 331 ) ≡ 98 ⋅ ( 98 2 ) 82 ( mod 331 ) ≡ 98 ⋅ 5 82 ( mod 331 ) ≡ 98 ⋅ 25 41 ( mod 331 ) ≡ 133 ⋅ 25 40 ( mod 331 ) ≡ 133 ⋅ 294 20 ( mod 331 ) ≡ 133 ⋅ 45 10 ( mod 331 ) ≡ 133 ⋅ 39 5 ( mod 331 ) ≡ 222 ⋅ 39 4 ( mod 331 ) ≡ 222 ⋅ 197 2 ( mod 331 ) ≡ 222 ⋅ 82 ( mod 331 ) ≡ − 1 ( mod 331 ) {\displaystyle {\begin{aligned}\left({\frac {98}{331}}\right)&\equiv 98^{\frac {331-1}{2}}&{\pmod {331}}\\&\equiv 98^{165}&{\pmod {331}}\\&\equiv 98\cdot (98^{2})^{82}&{\pmod {331}}\\&\equiv 98\cdot 5^{82}&{\pmod {331}}\\&\equiv 98\cdot 25^{41}&{\pmod {331}}\\&\equiv 133\cdot 25^{40}&{\pmod {331}}\\&\equiv 133\cdot 294^{20}&{\pmod {331}}\\&\equiv 133\cdot 45^{10}&{\pmod {331}}\\&\equiv 133\cdot 39^{5}&{\pmod {331}}\\&\equiv 222\cdot 39^{4}&{\pmod {331}}\\&\equiv 222\cdot 197^{2}&{\pmod {331}}\\&\equiv 222\cdot 82&{\pmod {331}}\\&\equiv -1&{\pmod {331}}\end{aligned}}}

utilizando el cuadrado repetido módulo 331, reduciendo cada valor usando el módulo después de cada operación para evitar el cálculo con números enteros grandes.

Notas

  1. ^ Legendre, AM (1798). Ensayo sobre la teoría de los nombres. París. pag. 186.
  2. ^ Hardy y Wright, Tesis 83.
  3. ↑ Ribenboim, pág. 64; Lemmermeyer, ej. 2.25–2.28, págs. 73–74.
  4. ^ Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reimpreso en Untersuchungen... págs.
  5. ^ Gauss, "Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den quadratischen Resten" (1818) reimpreso en Untersuchungen... págs. 501–505
  6. ^ Lemmermeyer, pág. 31, 1.34
  7. ^ Lemmermeyer, págs. 236 y siguientes.

Referencias

  • Calculadora del símbolo de Jacobi
Retrieved from "https://en.wikipedia.org/w/index.php?title=Legendre_symbol&oldid=1236957834"