Símbolo de leyenda

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

El símbolo de Legendre fue introducido por Adrien-Marie Legendre en 1798 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 notacional del símbolo de Legendre inspiró la introducción de varios otros "símbolos" utilizado en la teoría algebraica de números, como el símbolo de Hilbert y el símbolo de Artin.

Definición

Vamos p{displaystyle p} ser un número impar. Un entero a{displaystyle a} es un modulo de residuos cuadráticos p{displaystyle p} si es congruente con un modulo cuadrado perfecto p{displaystyle p} y es un modulo no residual cuadrático p{displaystyle p} De lo contrario. El Signatura Legendre es una función a{displaystyle a} y p{displaystyle p} definidas

()ap)={}1siaes un modulo de residuos cuadráticospya≢0()modp),− − 1siaes un modulo de residuos no cuadráticop,0sia↑ ↑ 0()modp).{displaystyle left({frac {} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {f}f}fnMicrosoft}fnMicrosoft Sans}fnMicrosoft Sans Serif}fnMicrosoft Sans Serif}fnMicrosoft Sans {fnMicrosoft Sans {fnMicrosoft Sans}fnMicrosoft Sans Serif}fnMicrosoft Sans Serif}fnMicrosoft Sans}fnMicrosoft Sans#

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

()ap)↑ ↑ ap− − 12()modp)y()ap)▪ ▪ {}− − 1,0,1}.{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}} {cH0}} {cH0}} {ccH0}} {cH0}}}cccH0}}cccH0}}}}cccccccccccccccccccccccccccccccccccccccccccccccccccccccccH0}}cccccccccccccc

Por el criterio de Euler, que había sido descubierto antes y era conocido por Legendre, estas dos definiciones son equivalentes. Así la contribución de Legendre radicaba en introducir un conveniente notación que registró la resistencia cuadrática amodp. Por el bien de la comparación, Gauss utilizó la notación aRp, aNp según si a es un residuo o un modulo no residual p. Para comodidad tipográfica, el símbolo Legendre a veces está escrito como (aSilenciop) o (a/p). Para fijar p, la secuencia ()0p),()1p),()2p),...... {displaystyle left({tfrac {0}{p}right),left({tfrac {1}{p}}right),left({tfrac {2}{p}right),ldots } es periódica con el período p y a veces se llama Secuencia de leyendas. Cada fila en la tabla siguiente muestra la periodicidad, tal como se describe.

Tabla de valores

Lo siguiente es una tabla de valores del símbolo Legendre ()ap){displaystyle left({frac {p}right)} con p≤ 127, a≤ 30, p imparable.

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 g▪ ▪ FpAlternativa Alternativa {displaystyle gin mathbb {fnK}, si x=gr{displaystyle x=g^{r}, entonces x{displaystyle x} es un residuo cuadrático si y sólo si r{displaystyle r} es incluso. Esto muestra que la mitad de los elementos no cero en FpAlternativa Alternativa {displaystyle mathbb {F} _{}{*}} son residuos cuadráticos.
• Si p↑ ↑ 3mod4{displaystyle pequiv 3{ mod }4} entonces el hecho de que

  p+14+p+14=()p− − 1)+22{fnMicroc} {p+1}{4}+{frac} {p+1}{4}={frac {(p-1)+2}{2}} nos da eso a=x()p+1)/4{displaystyle a=x^{(p+1)/4} es la raíz cuadrada del residuo cuadrático x{displaystyle x}.

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

  ()ap)=()bp).{displaystyle left({frac {fnK}derecha)=left({frac {b}derecha).}

• El símbolo Legendre es una función completamente multiplicadora de su argumento superior:

  ()abp)=()ap)()bp).{displaystyle left({frac {ab}{p}right)=left({frac {fnMicrosoft Sans Serif} {b} {p}right).}

• En particular, el producto de dos números que son residuos cuadráticos o modulos no residuos cuadráticos 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 Legendre de una plaza:

  ()x2p)={}1sip∤ ∤ x0sip▪ ▪ x.{displaystyle left({frac {x^{2}{p}}right)={begin{cases}1 {mbox{if} }pnmid x âmbox{if }pmid x.end{cases}}

• Cuando se ve como una función a, el símbolo Legendre ()ap){displaystyle left({frac {p}right)} es el cuadrático único (o el orden) 2) Modulo de caracteres dirichlet p.
• El primer suplemento a la ley de reciprocidad cuadrática:

  ()− − 1p)=()− − 1)p− − 12={}1sip↑ ↑ 1()mod4)− − 1sip↑ ↑ 3()mod4).{displaystyle left({frac {-1}{}right)=(-1)^{frac {p-1}{2}={begin{cases}1 limit{mbox{ if }pequiv 1{pmod {4}}\\1 golpe{mbox{ if }pequiv 3{pmod {4}.end{cases}}}}}}}}}} {p1} {p1} {p1}}}}}}}}}} {pp1}}}}}}ppppp1}} {pp1} {pppppp1}{p1}}}}}}}}}}}}}}}}}}pppppppppppppppppppppppp1}{p1}}}}}}ppppppppp

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

  ()2p)=()− − 1)p2− − 18={}1sip↑ ↑ 1o7()mod8)− − 1sip↑ ↑ 3o5()mod8).{displaystyle left({frac {2}{p}right)=(-1)^{tfrac {p^{2}-1}{8}={begin{cases}1 limit{mbox{ if }pequiv 1{mbox{ or }}}7{pmod {8}\1}{mbox{ if }pequiv 3{mbox{ or }}}5{pmod {8}}pend{f}{f}{mbox}} {}}}}}}}}p}pp}ppp}{cccccccccccccccccccccccccccccccccccccccccccccH00}ccccccH00}ccccccc

• Fórmulas especiales para el símbolo Legendre ()ap){displaystyle left({frac {p}right)} para valores pequeños a:
  • Para una prima extraña pل 3,

    ()3p)=()− − 1)⌊p+16⌋={}1sip↑ ↑ 1o11()mod12)− − 1sip↑ ↑ 5o7()mod12).{displaystyle left({frac {3}{p}right)=(-1)^{big lfloor }{frac}{frac {p+1}{6}{big rfloor {fnMicrosoft Sans Serif}= {fnMicrosoft Sans Serif}}\mbox{mbox{ or }}11{pmod {12}}\\1}\mbox{ if }pequiv 5{mbox{ or }}7{pmod {12}}}}}end{cases}}}}}}} {f}}}}} {f}}}}} {ppppppppbegin {begin {pppbegin {begin{pppppppbegin {begin {begin {begin {ppbegin {begin{pppbegin {fncip}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} {ppp

  • Para una prima extraña pل 5,

    ()5p)=()− − 1)⌊2p+25⌋={}1sip↑ ↑ 1o4()mod5)− − 1sip↑ ↑ 2o3()mod5).{displaystyle left({frac {5}{p}right)=(-1)^{big lfloor }{frac {2p+2}{5}{big rfloor {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}}}\fnMicrosoft {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}}} {fnMicrosoft Sans}}}} {fnMicros}}}}}}}}}}}}}}}}}} {fnMientrossssigualmam}} {fnMientras que no erasigues}}}}fnunts} {fnunfncipes} {fnuntfnun}}fnun}fnunfnunfnunfnunfnunfnun}fnMinun}fnMinMinunfnun}}}}fnMien

• Los números Fibonacci 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

  Fp− − ()p5)↑ ↑ 0()modp),Fp↑ ↑ ()p5)()modp).{displaystyle F_{p-left({frac Equiv 0{pmod {p}qquad F_{p}equiv left({frac {p}right){pmod {p}}

Por ejemplo,

()25)=− − 1,F3=2,F2=1,()35)=− − 1,F4=3,F3=2,()55)=0,F5=5,()75)=− − 1,F8=21,F7=13,()115)=1,F10=55,F11=89.{displaystyle {begin{aligned}left({tfrac {2}{5} {5} {}}} {}}}} {}}}}} {2} {}}}}} {c}} {c}}}}}}}}}}cccH0} {cH0}} {c}}}} {c}}} {}}}} {c}}}}}}} {c}}}} {c}}}}}}}}}}}} {cc}}}}}}}}}}} {cc}}} {cc}}}}}}}}}}} {cc}}}}}}}} {c}}}}} {cccccccccccccccccccccccccccccccccccc}}}}

• Este resultado proviene de la teoría de las secuencias de Lucas, que se utilizan en pruebas de primalidad. Ver Wall–Sun–Sun prime.

Símbolo de leyenda y reciprocidad cuadrática

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

()qp)()pq)=()− − 1)p− − 12⋅ ⋅ q− − 12.{displaystyle left({frac {q} {p}right)left({frac} {fnK}right)=(-1)}{{tfrac {p-1}{2}cdot {tfrac} {q-1}{2}}}}

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

()ap)↑ ↑ ap− − 12()modp).{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 varias pruebas de la ley de reciprocidad cuadrática.

• Gauss introdujo la suma de Gauss quadratic y utilizó la fórmula

.. k=0p− − 1Especificaciones Especificaciones ak2=()ap).. k=0p− − 1Especificaciones Especificaciones k2,Especificaciones Especificaciones =e2π π ip{displaystyle sum _{k=0}{p-1}zeta ^{ak^{2}=left({frac {a}{p}right)sum ¿Qué? ^{k^{2}},qquad zeta =e^{frac {2ccH00} - Sí.

en sus pruebas cuarta y sexta de reciprocidad cuadrática.

• La prueba de Kronecker primero establece que

()pq)=Sgn⁡ ⁡ ()∏ ∏ i=1q− − 12∏ ∏ k=1p− − 12()kp− − iq)).{displaystyle left({frac {p}{q}right)=operatorname {sgn} left(prod) - ¿Por qué? {q-1}{2}prod {fnMicroc {fnMicroc}left({frac} {k} {p}-{frac} {i}{q}right)right).}

Revertir las funciones de p y q, obtiene la relación entre (p/q) y (q/p).

• Una de las pruebas de Eisenstein comienza mostrando que

()qp)=∏ ∏ n=1p− − 12pecado⁡ ⁡ ()2π π qnp)pecado⁡ ⁡ ()2π π np).{displaystyle left({frac {q}{p}right)=prod {fn=1}frac {fn}{2}{frac {sin left({frac {2pi qn}{p}}right)}{sin left({frac {2pi n}{p}right)}}}}}}

Usando ciertas funciones elípticas en lugar de la función sine, Eisenstein fue capaz de demostrar reciprocidad cúbica y cuártica también.

Funciones relacionadas

• El símbolo Jacobia/n) es una generalización del símbolo Legendre que permite un segundo compuesto (abajo) argumento n, aunque n debe seguir siendo extraño y positivo. Esta generalización proporciona una manera eficiente de calcular todos los símbolos Legendre sin realizar la factorización a lo largo del camino.
• Otra extensión es el símbolo Kronecker, en el que el argumento inferior puede ser cualquier entero.
• El símbolo de residuos de energía (a/n)_n generaliza el símbolo Legendre al poder superior n. El símbolo Legendre representa el símbolo de residuo de poder 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:

()12345331)=()3331)()5331)()823331)=()3331)()5331)()161331)=()3331)()5331)()7331)()23331)=()− − 1)()3313)()3315)()− − 1)()3317)()− − 1)()33123)=− − ()13)()15)()27)()923)=− − ()13)()15)()27)()3223)=− − ()1)()1)()1)()1)=− − 1.{fnMicrosoft Sans Serif} {2}{2}{7}right)left({frac {9}{23}}right)\cccccccc}ccH0}ccH3}cH00}ccH00}cH00} {cH00}cH00}cH00} {cH00}cH00}cH00}cH00}cH00}cH00}cH00}}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cccH00}cH00}cH00}cH00}}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cH00}cccH00}

O usando un cálculo más eficiente:

()12345331)=()98331)=()2⋅ ⋅ 72331)=()2331)=()− − 1)3312− − 18=− − 1.{displaystyle left {frac {12345}{331}right)=left({frac {98}{331}}right)=left({frac {2cdot 7^{2}{331}right)=left({frac {2}{331}{331}right)=-1)= {331}=-1.}

El artículo Símbolo de Jacobi tiene más ejemplos de manipulación de símbolos 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 usar la definición original de Legendre, p.

()98331)↑ ↑ 98331− − 12()mod331)↑ ↑ 98165()mod331)↑ ↑ 98⋅ ⋅ ()982)82()mod331)↑ ↑ 98⋅ ⋅ 582()mod331)↑ ↑ 98⋅ ⋅ 2541()mod331)↑ ↑ 133⋅ ⋅ 2540()mod331)↑ ↑ 133⋅ ⋅ 29420()mod331)↑ ↑ 133⋅ ⋅ 4510()mod331)↑ ↑ 133⋅ ⋅ 395()mod331)↑ ↑ 222⋅ ⋅ 394()mod331)↑ ↑ 222⋅ ⋅ 1972()mod331)↑ ↑ 222⋅ ⋅ 82()mod331)↑ ↑ − − 1()mod331){fnMicrosoft}

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