símbolo de leyenda

Función en 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 módulo de carácter cuadrático de un número primo impar p : su valor en un residuo cuadrático mod  p (distinto de cero) es 1 y en un El residuo 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 la 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 algebraica de números , como el símbolo de Hilbert y el símbolo de Artin .

Definición

Sea un número primo impar . Un número entero es un módulo de residuo cuadrático si es congruente con un módulo de cuadrado perfecto y, en caso contrario, es un módulo de residuo cuadrático . El símbolo de Legendre es una función 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 , descubierto anteriormente y conocido por Legendre, estas dos definiciones son equivalentes. ^[2] Así, la contribución de Legendre consistió en introducir una notación conveniente que registraba la residuosidad cuadrática de un  mod  p . A modo de comparación, Gauss utilizó la notación a R p , a N p según si a es un módulo p residual o no residual . 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 le llama 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 usarse para calcularlo de manera eficiente.

• Dado un generador , si , entonces es un residuo cuadrático si y sólo si es par. Esto muestra que la mitad de los elementos 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 la 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 (o superior) argumento: 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 ve como una función de a , el símbolo de Legendre es el único carácter cuadrático (u orden 2) de Dirichlet 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 Muro-Sol-Sol principal .

Símbolo de Legendre y reciprocidad cuadrática

Sean p y q números primos impares distintos. Usando el símbolo de Legendre, la ley de reciprocidad cuadrática se puede expresar de manera 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 cuadrática de Gauss 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 sus pruebas cuarta ^[4] y sexta ^[5] 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) , aunque n aún debe ser impar y positivo. Esta generalización proporciona una manera eficiente de calcular todos los símbolos de Legendre sin realizar factorización en el camino.
• 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 de residuo de energía (a/norte) _n generaliza el símbolo de Legendre a una potencia superior n . El símbolo de Legendre representa el símbolo del residuo de poder 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 usando 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}}}$

usando el módulo de elevación al cuadrado repetido 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, Thm. 83.
3. Ribenboim, pag. 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, ej. pag. 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 de símbolos de Jacobi