# Símbolo de Legendre

Símbolo de Legendre (ap) para vários a (ao longo do topo) e p (ao longo do lado esquerdo). :
| ap | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 3 | 0 | 1 | −1 | | | | | | | | |
| 5 | 0 | 1 | −1 | −1 | 1 | | | | | | |
| 7 | 0 | 1 | 1 | −1 | 1 | −1 | −1 | | | | |
| 11 | −0 | −1 | −1 | 1 | −1 | 1 | −1 | −1 | −1 | −1 | −1 |
| Apenas 0 ≤ a < p são mostrados, uma vez que devido à primeira propriedade abaixo qualquer outro a pode ser módulo p reduzido. Os resíduos quadráticos são destacados em amarelo e correspondem precisamente aos valores 0 e 1. ||||||||||||
Na teoria dos números, o símbolo de Legendre é uma função multiplicativa com os valores 1, -1, 0 que é um módulo de caráter quadrático de um número primo ímpar p: seu valor em um resíduo quadrático (diferente de zero) mod p é 1 e em um não resíduo quadrático (que não é resíduo) mod p é -1. Seu valor em zero é 0.
O símbolo de Legendre foi introduzido por Adrien-Marie Legendre, em 1798,no curso de suas tentativas de provar a lei da reciprocidade quadrática. As generalizações do símbolo incluem o símbolo de Jacobi e os carateres de Dirichlet de ordem superior. A conveniência de notação do símbolo de Legendre inspirou a introdução de vários outros "símbolos" usados na teoria algébrica dos números, como o símbolo de Hilbert [en] e o símbolo de Artin [en].

## Definição

Seja $p$ um número primo ímpar. Um inteiro $a$ é um resíduo quadrático módulo $p$ se for congruente a um quadrado perfeito módulo $p$ e ,caso não, é um não resíduo quadrático módulo $p$. O símbolo de Legendre é uma função de $a$ e $p$ definida como
    $\left({\frac {a}{p}}\right)={\begin{cases}1&{\text{se }}a{\text{ é um resíduo quadrático modulo }}p{\text{ e }}a\not \equiv 0{\pmod {p}},\\-1&{\text{se }}a{\text{ é um não resíduo quadrático modulo }}p,\\0&{\text{se }}a\equiv 0{\pmod {p}}.\end{cases}}$
A definição original de Legendre era por meio da 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\}.$
Pelo Critério de Euler, que foi descoberto anteriormente e era conhecido por Legendre, essas duas definições são equivalentes. Assim, a contribuição de Legendre consistiu na introdução de uma notação conveniente que registrou a residuosidade quadrática de a mod p. Para efeito de comparação, Gauss usou a notação aRp, aNp de acordo com se a é um resíduo ou não resíduo módulo p. Por conveniência tipográfica, o símbolo de Legendre às vezes é escrito como (a|p) ou (a/p). Para p fixo, a sequência $\left({\tfrac {0}{p}}\right),\left({\tfrac {1}{p}}\right),\left({\tfrac {2}{p}}\right),\ldots$ é periódica [en] com período p e às vezes é chamada de sequência de Legendre. Cada linha da tabela a seguir exibe periodicidade, conforme descrito.

## Tabela de valores

A seguir está uma tabela de valores do símbolo de Legendre $\left({\frac {a}{p}}\right)$ com p ≤ 127, a ≤ 30, p primo ímpar.
| ap | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| 3 | −1 | −1 | 0 | −1 | −1 | 0 | 1 | −1 | −0 | 1 | −1 | 0 | 1 | −1 | 0 | −1 | −1 | 0 | 1 | −1 | 0 | 1 | −1 | 0 | −1 | −1 | 0 | 1 | −1 | 0 |
| 5 | 1 | −1 | −1 | 1 | 0 | 1 | −1 | −1 | 1 | 0 | 1 | −1 | −1 | 1 | 0 | 1 | −1 | −1 | 1 | 0 | 1 | −1 | −1 | 1 | 0 | 1 | −1 | −1 | 1 | 0 |
| 7 | 1 | 1 | −1 | 1 | −1 | −1 | 0 | 1 | 1 | −1 | 1 | −1 | −1 | 0 | 1 | 1 | −1 | 1 | −1 | −1 | 0 | 1 | 1 | −1 | 1 | −1 | −1 | 0 | 1 | 1 |
| 11 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 0 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 0 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 |
| 13 | 1 | −1 | 1 | 1 | −1 | −1 | −1 | −1 | 1 | 1 | −1 | 1 | 0 | 1 | −1 | 1 | 1 | −1 | −1 | −1 | −1 | 1 | 1 | −1 | 1 | 0 | 1 | −1 | 1 | 1 |
| 17 | 1 | 1 | −1 | 1 | −1 | −1 | −1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | 1 | 0 | 1 | 1 | −1 | 1 | −1 | −1 | −1 | 1 | 1 | −1 | −1 | −1 | 1 |
| 19 | 1 | −1 | −1 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | −1 | −1 | −1 | −1 | 1 | 1 | −1 | 0 | 1 | −1 | −1 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 |
| 23 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | 1 | −1 | −1 | 1 | 1 | −1 | −1 | 1 | −1 | 1 | −1 | −1 | −1 | −1 | 0 | 1 | 1 | 1 | 1 | −1 | 1 | −1 |
| 29 | 1 | −1 | −1 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | −1 | −1 | 1 | −1 | −1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | 1 | 1 | 1 | −1 | −1 | 1 | 0 | 1 |
| 31 | 1 | 1 | −1 | 1 | 1 | −1 | 1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | −1 | 1 | −1 | −1 | 1 | −1 | −1 |
| 37 | 1 | −1 | 1 | 1 | −1 | −1 | 1 | −1 | 1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | −1 | −1 | −1 | 1 | −1 | −1 | −1 | 1 | 1 | 1 | 1 | −1 | 1 |
| 41 | 1 | 1 | −1 | 1 | 1 | −1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | −1 | −1 | 1 | −1 | 1 | −1 | 1 | 1 | −1 | 1 | −1 | 1 | −1 | −1 | −1 | −1 | −1 |
| 43 | 1 | −1 | −1 | 1 | −1 | 1 | −1 | −1 | 1 | 1 | 1 | −1 | 1 | 1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | −1 | −1 |
| 47 | 1 | 1 | 1 | 1 | −1 | 1 | 1 | 1 | 1 | −1 | −1 | 1 | −1 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | 1 | −1 | −1 | 1 | 1 | −1 | 1 | 1 | −1 | −1 |
| 53 | 1 | −1 | −1 | 1 | −1 | 1 | 1 | −1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | −1 | −1 | −1 | 1 | 1 | −1 | −1 | 1 | 1 | −1 |
| 59 | 1 | −1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | −1 | −1 | 1 | −1 | −1 | 1 | 1 | 1 | −1 | 1 | 1 | 1 | 1 | −1 | −1 | 1 | 1 | 1 | 1 | 1 | −1 |
| 61 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | −1 | 1 | 1 | 1 | 1 | 1 | −1 | −1 | 1 | 1 | −1 | 1 | −1 | −1 | 1 | −1 | 1 | −1 | −1 | −1 |
| 67 | 1 | −1 | −1 | 1 | −1 | 1 | −1 | −1 | 1 | 1 | −1 | −1 | −1 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | 1 | 1 | 1 | 1 | 1 | −1 | −1 | 1 | −1 |
| 71 | 1 | 1 | 1 | 1 | 1 | 1 | −1 | 1 | 1 | 1 | −1 | 1 | −1 | −1 | 1 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | 1 | −1 | 1 | −1 | 1 | 1 |
| 73 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | 1 | −1 | −1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | 1 | −1 | −1 | −1 | 1 | 1 | 1 | −1 | 1 | −1 | −1 | −1 |
| 79 | 1 | 1 | −1 | 1 | 1 | −1 | −1 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | −1 | 1 | −1 | 1 | 1 | 1 | 1 | 1 | 1 | −1 | 1 | 1 | −1 | −1 | −1 | −1 |
| 83 | 1 | −1 | 1 | 1 | −1 | −1 | 1 | −1 | 1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | −1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 89 | 1 | 1 | −1 | 1 | 1 | −1 | −1 | 1 | 1 | 1 | 1 | −1 | −1 | −1 | −1 | 1 | 1 | 1 | −1 | 1 | 1 | 1 | −1 | −1 | 1 | −1 | −1 | −1 | −1 | −1 |
| 97 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | 1 | −1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | 1 | −1 | 1 | −1 | −1 | −1 |
| 101 | 1 | −1 | −1 | 1 | 1 | 1 | −1 | −1 | 1 | −1 | −1 | −1 | 1 | 1 | −1 | 1 | 1 | −1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | −1 | −1 | −1 | −1 | 1 |
| 103 | 1 | 1 | −1 | 1 | −1 | −1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | 1 | −1 | 1 | 1 | 1 |
| 107 | 1 | −1 | 1 | 1 | −1 | −1 | −1 | −1 | 1 | 1 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | −1 | 1 | −1 | −1 | −1 | 1 | −1 | 1 | −1 | 1 | −1 | 1 | 1 |
| 109 | 1 | −1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | −1 | −1 | 1 | −1 | −1 | 1 | 1 | −1 | −1 | −1 | 1 | 1 | 1 | −1 | −1 | 1 | 1 | 1 | 1 | 1 | −1 |
| 113 | 1 | 1 | −1 | 1 | −1 | −1 | 1 | 1 | 1 | −1 | 1 | −1 | 1 | 1 | 1 | 1 | −1 | 1 | −1 | −1 | −1 | 1 | −1 | −1 | 1 | 1 | −1 | 1 | −1 | 1 |
| 127 | 1 | 1 | −1 | 1 | −1 | −1 | −1 | 1 | 1 | −1 | 1 | −1 | 1 | −1 | 1 | 1 | 1 | 1 | 1 | −1 | 1 | 1 | −1 | −1 | 1 | 1 | −1 | −1 | −1 | 1 |

## Propriedades do símbolo Legendre

Existem várias propriedades úteis do símbolo de Legendre que, juntamente com a lei da reciprocidade quadrática, podem ser usadas para o computar de forma eficiente.
* Dado um gerador $g\in \mathbb {F} _{p}^{*}$, se $x=g^{r}$, então $x$ é um resíduo quadrático se e somente se $r$ for par. Isso também mostra que metade dos elementos diferentes de zero em $\mathbb {F} _{p}^{*}$ são resíduos quadráticos.
* Se $p\equiv 3{\text{ mod }}4$ então o fato de que
    ${\frac {p+1}{4}}+{\frac {p+1}{4}}={\frac {(p-1)+2}{2}}$ nos dá que $a=x^{(p+1)/4}$ é a raiz quadrada do resíduo quadrático $x$.
* O símbolo de Legendre é periódico em seu primeiro (ou superior) argumento: se a ≡ b (mod p), então
    $\left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right).$
* O símbolo de Legendre é uma função completamente multiplicativa de seu argumento principal:
    $\left({\frac {ab}{p}}\right)=\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right).$
* Em particular, o produto de dois números que são ambos resíduos quadráticos ou não resíduos quadráticos módulo p é um resíduo, enquanto o produto de um de resíduo com um não resíduo é um não é resíduo. Um caso especial é o símbolo de Legendre de um quadrado:
    $\left({\frac {x^{2}}{p}}\right)={\begin{cases}1&{\mbox{se }}p\nmid x\\0&{\mbox{se }}p\mid x.\end{cases}}$
* Quando visto como uma função de a, o símbolo de Legendre $\left({\frac {a}{p}}\right)$ é o único caráter de Dirichlet quadrático (ou de ordem 2) módulo p.
* O primeiro suplemento à lei da reciprocidade quadrática:
    $\left({\frac {-1}{p}}\right)=(-1)^{\frac {p-1}{2}}={\begin{cases}1&{\mbox{ se }}p\equiv 1{\pmod {4}}\\-1&{\mbox{ se }}p\equiv 3{\pmod {4}}.\end{cases}}$
* O segundo suplemento à lei da reciprocidade quadrática:
    $\left({\frac {2}{p}}\right)=(-1)^{\tfrac {p^{2}-1}{8}}={\begin{cases}1&{\mbox{ se }}p\equiv 1{\mbox{ ou }}7{\pmod {8}}\\-1&{\mbox{ se }}p\equiv 3{\mbox{ ou }}5{\pmod {8}}.\end{cases}}$
* Fórmulas especiais para o símbolo de Legendre $\left({\frac {a}{p}}\right)$ para pequenos valores de a:
** Para um primo ímpar 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 um primo ímpar 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{ or }}4{\pmod {5}}\\-1&{\mbox{ se }}p\equiv 2{\mbox{ or }}3{\pmod {5}}.\end{cases}}$
* Os números de Fibonacci 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … são definidos pela recorrência F$_1$ = F$_2$ = 1, F$_{n+1}$ = F$_n$ + F$_{n−1}$. Se p é um número primo, então
    $F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p}},\qquad F_{p}\equiv \left({\frac {p}{5}}\right){\pmod {p}}.$
    Por exemplo,
       ${\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 vem da teoria das sequências de Lucas, que são usadas em testes de primalidade. Veja o artigo sobre os Primos de Wall–Sun–Sun.

## Símbolo de Legendre e reciprocidade quadrática

Sejam p e q primos ímpares distintos. Usando o símbolo de Legendre, a lei de reciprocidade quadrática pode ser declarada de forma concisa:
    $\left({\frac {q}{p}}\right)\left({\frac {p}{q}}\right)=(-1)^{{\tfrac {p-1}{2}}\cdot {\tfrac {q-1}{2}}}.$
Muitas provas de reciprocidade quadrática [en] são baseadas no Critério de Euler
    $\left({\frac {a}{p}}\right)\equiv a^{\tfrac {p-1}{2}}{\pmod {p}}.$
Além disso, várias expressões alternativas para o símbolo de Legendre foram concebidas a fim de produzir várias provas da lei de reciprocidade quadrática.
* Gauss introduziu a soma quadrática de Gauss e usou 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}}$
    em sua quarta e sexta provas de reciprocidade quadrática.
A prova de Kronecker primeiro estabelece que
       $\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).$
Invertendo as funções de p e q, ele obtém a relação entre (pq) e (qp)
Uma das provas de Eisenstein começa mostrando que
       $\left({\frac {q}{p}}\right)=\prod _{n=1}^{\frac {p-1}{2}}{\frac {\operatorname {sen} \left({\frac {2\pi qn}{p}}\right)}{\operatorname {sen} \left({\frac {2\pi n}{p}}\right)}}.$
Usando certas funções elípticas em vez da função seno, Eisenstein foi capaz de provar as reciprocidades cúbica [en] e quártica [en] também.

## Funções relacionadas

* O símbolo de Jacobi (an) é uma generalização do símbolo de Legendre que permite um segundo argumento composto (inferior) n, embora n ainda deva ser ímpar e positivo. Essa generalização fornece uma maneira eficiente de calcular todos os símbolos de Legendre sem realizar a fatoração ao longo do caminho.
* Uma extensão adicional é o símbolo de Kronecker, no qual o argumento inferior pode ser qualquer número inteiro.
* O símbolo de resíduo de potência [en] (an)$_n$ generaliza o símbolo de Legendre para a maior potência n. O símbolo de Legendre representa o símbolo de resíduo de potência [en] para n = 2.

## Exemplo computacional

As propriedades acima, incluindo a lei da reciprocidade quadrática, podem ser usadas para avaliar qualquer símbolo de Legendre. Por exemplo:
    ${\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}}$
Ou usando um cálculo mais 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.$
O artigo sobre o Símbolo de Jacobi tem mais exemplos de manipulação de símbolos de Legendre.
Como nenhum algoritmo de fatoração eficiente é conhecido, mas algoritmos de exponenciação modular [en] eficientes são, em geral, é mais eficiente usar a definição original de Legendre, por exemplo
    ${\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 quadratura repetida [en] módulo 331, reduzindo cada valor usando o módulo após cada operação para evitar computação com números inteiros grandes.