Símbolo de Legendre

Función en la teoría de números

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 ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle a}$ ${\displaystyle p}$

${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}1&{\text{if }}a{\text{ is a quadratic residue modulo }}p{\text{ and }}a\not \equiv 0{\pmod {p}},\\-1&{\text{if }}a{\text{ is a quadratic nonresidue modulo }}p,\\0&{\text{if }}a\equiv 0{\pmod {p}}.\end{cases}}}$

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

${\displaystyle \left({\frac {a}{p}}\right)\equiv a^{\frac {p-1}{2}}{\pmod {p}}\quad {\text{ and }}\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. ${\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. ${\displaystyle \left({\frac {a}{p}}\right)}$

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. ${\displaystyle g\in \mathbb {F} _{p}^{*}}$ ${\displaystyle x=g^{r}}$ ${\displaystyle x}$ ${\displaystyle r}$ ${\displaystyle \mathbb {F} _{p}^{*}}$
• Si entonces el hecho de que ${\displaystyle p\equiv 3{\text{ mod }}4}$

  ${\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 . ${\displaystyle a=x^{(p+1)/4}}$ ${\displaystyle x}$

• El símbolo de Legendre es periódico en su primer argumento (o superior): si a ≡ b (mod p ), entonces

  ${\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:

  ${\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:

  ${\displaystyle \left({\frac {x^{2}}{p}}\right)={\begin{cases}1&{\mbox{if }}p\nmid x\\0&{\mbox{if }}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 . ${\displaystyle \left({\frac {a}{p}}\right)}$
• El primer suplemento a la ley de reciprocidad cuadrática:

  ${\displaystyle \left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}1&{\mbox{ if }}p\equiv 1{\pmod {4}}\\-1&{\mbox{ if }}p\equiv 3{\pmod {4}}.\end{cases}}}$

• El segundo suplemento a la ley de reciprocidad cuadrática:

  ${\displaystyle \left({\frac {2}{p}}\right)=(-1)^{\tfrac {p^{2}-1}{8}}={\begin{cases}1&{\mbox{ if }}p\equiv 1{\mbox{ or }}7{\pmod {8}}\\-1&{\mbox{ if }}p\equiv 3{\mbox{ or }}5{\pmod {8}}.\end{cases}}}$

• Fórmulas especiales para el símbolo de Legendre para valores pequeños de a : ${\displaystyle \left({\frac {a}{p}}\right)}$
  • Para un primo impar p  ≠ 3,

    ${\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,

    ${\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 ₁ = F ₂ = 1, F _{n +1} = F _n + F _{n −1} . Si p es un número primo entonces

  ${\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,

${\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}}}$

• Este resultado proviene de la teoría de las secuencias de Lucas , que se utilizan en las pruebas de primalidad . ^[3] Véase primo Wall–Sun–Sun .

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:

${\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.

${\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.

• Gauss introdujo la suma gaussiana cuadrática y utilizó la fórmula

${\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.

• La prueba de Kronecker ^[6] establece primero que

${\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

${\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 .

Funciones relacionadas

• 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:

${\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:

${\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

${\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

• Gauss, Carl Friedrich (1965), Untersuchungen über höhere Arithmetik (Disquisitiones Arithmeticae y otros artículos sobre teoría de números) , traducido por Maser, H. (Segunda ed.), Nueva York: Chelsea, ISBN 0-8284-0191-8
• Gauss, Carl Friedrich (1986), Disquisitiones Arithmeticae , traducido por Clarke, Arthur A. (segunda edición corregida), Nueva York: Springer , ISBN 0-387-96254-9
• Bach, Eric; Shallit, Jeffrey (1996), Teoría algorítmica de números , vol. I: Algoritmos eficientes), Cambridge: The MIT Press , ISBN 0-262-02405-5
• Hardy, GH ; Wright, EM (1980), Introducción a la teoría de números (Quinta edición) , Oxford: Oxford University Press , ISBN 978-0-19-853171-5
• Irlanda, Kenneth; Rosen, Michael (1990), Una introducción clásica a la teoría de números moderna (segunda ed.), Nueva York: Springer , ISBN 0-387-97329-X
• Lemmermeyer, Franz (2000), Leyes de reciprocidad: de Euler a Eisenstein , Berlín: Springer , ISBN 3-540-66957-4
• Ribenboim, Paulo (1996), El nuevo libro de registros de números primos , Nueva York: Springer , ISBN 0-387-94457-5

Enlaces externos

• Calculadora del símbolo de Jacobi