Símbolo de Legendre

En teoría de números, o **símbolo de Legendre** é unha función multiplicativa con valores \{1, -1, 0\} que é un  carácter cadrático módulo un número primo impar p: o seu valor para un residuo cadrático (non cero) \mod p é 1 e para un residuo non cadrático (un *non residuo*) é -1. O seu valor en cero é 0.

O símbolo de Legendre foi introducido por Adrien-Marie Legendre en 1798 no curso dos seus intentos de probar a lei da reciprocidade cadrática. As xeneralizacións do símbolo inclúen o símbolo de Jacobi e os caracteres de Dirichlet de orde superior. A conveniencia de notación do símbolo de Legendre inspirou a introdución doutros "símbolos" usados na teoría alxébrica de números, como o símbolo de Hilbert e o símbolo de Artin.

## Definición 
Sexa p un número primo impar. Un número enteiro a é un  residuo cadrático módulo p se é congruente cun  cadrado perfecto módulo p e é non residuo cadrático módulo p no caso contrario. O **símbolo de Legendre** é unha función de a e p definido como

: \left(\frac{a}{p}\right) = 
\begin{cases}
 1 & \text{se } a \text{ é un residuo cadrático módulo } p \text{ e } a \not\equiv 0\pmod p, \\
-1 & \text{se } a \text{ é un non residuo cadrático módulo } p, \\
 0 & \text{se } a \equiv 0 \pmod p.
\end{cases}

A definición orixinal de Legendre foi mediante a fórmula explícita

:  \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod p \quad \text{ e } \quad\left(\frac{a}{p}\right) \in \{-1,0,1\}. 

Segundo o criterio de Euler, que fora descuberto antes e que Legendre coñecía, estas dúas definicións son equivalentes. Así, a contribución de Legendre radicaba na introdución dunha *notación* conveniente que rexistrase residuos cadráticos de *a* mod *p*. Para comparar, Gauss utilizou a notación *a* R *p*, *a* N *p* segundo se *a* é un residuo ou un non residuo módulo *p*. Por comodidade tipográfica, o símbolo de Legendre ás veces escríbese como (*a* | *p*). Para un *p* fixo, a secuencia \left(\tfrac{0}{p}\right),\left(\tfrac{1}{p}\right),\left(\tfrac{2}{p}\right),\ldots é periódica con período *p* e ás veces chámase **secuencia de Legendre**. Cada fila da seguinte táboa presenta periodicidade, tal e como se describe.

## Táboa de valores 
A seguinte é unha táboa de valores do símbolo de Legendre \left(\frac{a}{p}\right) para *p* ≤ 127, *a* ≤ 30, *p* primo impar.

## Propiedades do símbolo de Legendre 
Hai unha serie de propiedades útiles do símbolo de Legendre que, xunto coa lei da reciprocidade cadrática, poden ser usadas para calculalo de forma eficiente.

* Dado un xerador g \in \mathbb{F}_p^*, se x = g^r, entón x é un residuo cadrático se e só se r é par. Isto mostra que a metade dos elementos en \mathbb{F}_p^* son residuos cadráticos.
* Se p \equiv 3 \text{ mod } 4 entón o feito de que 
*:  \frac{p+1}{4} + \frac{p+1}{4} = \frac{p+1}2 = \frac{(p-1)+2}{2} = \frac{p-1}2 + 1 dános que a = x^{(p+1)/4} é unha raíz cadrada do residuo cadrático x.
* O símbolo de Legendre é periódico no seu primeiro argumento (ou superior): se *a* ≡ *b* (mod *p*), entón 
*:  \left(\frac{a}{p}\right) = \left(\frac{b}{p}\right).
* O símbolo de Legendre é un función multiplicativa do seu argumento superior:
*: \left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right).
* En particular, o produto de dous números que son residuos cadráticos ou non residuos cadráticos módulo *p* é un residuo, mentres que o produto dun residuo cun non residuo é un non residuo. Un caso especial é o símbolo de Legendre dun cadrado:
*: \left(\frac{x^2}{p}\right) = \begin{cases} 1 & \mbox{se }p\nmid x\\ 0 & \mbox{se }p\mid x. \end{cases}
* Cando se ve como unha función de *a*, o símbolo de Legendre \left(\frac{a}{p}\right)  é o único carácter de Dirichlet cadrático (ou orde 2) módulo *p*.
* O primeiro suplemento á lei da reciprocidade cadrática:
*: \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}
* O segundo suplemento á lei da reciprocidade cadrática:
*:  \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 especiais para o símbolo de Legendre \left(\frac{a}{p}\right)  para valores pequenos de *a*:
** Para un primo impar *p* ≠ 3, 
**:  \left(\frac{3}{p}\right) = (-1)^{\big\lfloor \frac{p+1}{6}\big\rfloor} =
 \begin{cases}
   1 & \mbox{ se }p \equiv 1\mbox{ ou }11 \pmod{12} \\
  -1 & \mbox{ se }p \equiv 5\mbox{ ou }7 \pmod{12}.
 \end{cases}
** Para un primo impar *p* ≠ 5, 
**:  \left(\frac{5}{p}\right) =(-1)^{\big\lfloor \frac{2p+2}{5}\big \rfloor} =
 \begin{cases}
   1 & \mbox{ se }p \equiv 1\mbox{ ou }4 \pmod5 \\
  -1 & \mbox{ se }p \equiv 2\mbox{ ou }3 \pmod5.
 \end{cases}
* Os números de Fibonacci 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... son definidos pola recorrencia   Se *p* é un número primo daquela
*:  F_{p-\left(\frac{p}{5}\right)} \equiv 0 \pmod p, \qquad F_{p} \equiv \left(\frac{p}{5}\right) \pmod p.

* Este resultado provén da teoría das secuencias de Lucas, que se usan nos test de primalidade. Consulte primo de Wall–Sun–Sun.

## Símbolo de Legendre e reciprocidade cadrática 
Sexan *p* e *q* números primos impares distintos. Usando o símbolo de Legendre, a lei de reciprocidade cuadrática pódese enunciar concisamente:

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

Moitas probas da reciprocidade cadrática baséanse no criterio de Euler

: \left(\frac{a}{p}\right) \equiv a^{\tfrac{p-1}{2}} \pmod p.

* Gauss introduciu a suma cadrática de Gauss e utilizou a fórmula

:: \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}}

: na súa cuarta e sexta probas da reciprocidade cadrática.

## Funcións relacionadas 
* O símbolo de Jacobi () é unha xeneralización do símbolo de Legendre que permite un segundo argumento composto (inferior) *n*, aínda que *n*  debe ser impar e positivo. Esta xeneralización proporciona un xeito eficiente de calcular todos os símbolos de Legendre sen realizar a factorización.
* Outra extensión é o símbolo de Kronecker, no que o argumento inferior pode ser calquera número enteiro.
* O símbolo do residuo de potencia () xeneraliza o símbolo de Legendre a unha potencia superior *n*. O símbolo de Legendre representa o símbolo do residuo de potencia para *n* = 2.

## Exemplo computacional 
As propiedades anteriores, incluída a lei da reciprocidade cadrática, pódense usar para avaliar calquera símbolo de Legendre. Por exemplo:

: \begin{align}
\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{align}

Ou usando un cálculo máis eficiente:

: \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.

Dado que non se coñece un algoritmo de factorización eficiente, mais os algoritmos de exponenciación modular son eficientes, en xeral, é máis eficiente usar a definición orixinal de Legendre, por exemplo:

: \begin{align}
\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{align}

usando repetidamente o cadrado módulo 331, reducindo cada valor usando o módulo despois de cada operación para evitar o cálculo con enteiros grandes.
## Notas 
## Véxase tamén 
### Bibliografía 
* 
* 
* 
* 
* 
* 
* 

### Outros artigos 
* Símbolo de Jacobi.
* Teorema de Dirichlet sobre progresións aritméticas
### Ligazóns externas 
* calculadora de símbolos de Jacobi