Símbolo de Legendre

Seja ${\displaystyle p}$ um número primo ímpar. Um inteiro ${\displaystyle a}$ é um resíduo quadrático módulo ${\displaystyle p}$ se for congruente a um quadrado perfeito módulo ${\displaystyle p}$ e é um quadrático não residual módulo ${\displaystyle p}$ caso contrário. O símbolo de Legendre é uma função de ${\displaystyle a}$ e ${\displaystyle p}$ definida como

${\displaystyle \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 resíduo não 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

${\displaystyle \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.[2] 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). A sequência (a|p) para a igual a 0, 1, 2, ... é periódica com período p e às vezes é chamada de sequência de Legendre, com valores de {0,1,−1} ocasionalmente substituídos por {1,0,1} ou {0,1,0}.[3] Cada linha da tabela a seguir pode exibir periodicidade, conforme descrito.

A seguir está uma tabela de valores do símbolo de Legendre ${\displaystyle \left({\frac {a}{p}}\right)}$ com p ≤ 127, a ≤ 30, p primo ímpar.

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.

• O símbolo de Legendre revela a paridade de um inteiro diferente de zero mod p. Ou seja, dado um gerador ${\displaystyle g\in \mathbb {F} _{p}^{*}}$, se ${\displaystyle x=g^{r}}$ então ${\displaystyle x}$ é um resíduo quadrático se e somente se ${\displaystyle r}$ for par. Isso também mostra que metade dos elementos diferentes de zero em ${\displaystyle \mathbb {F} _{p}^{*}}$ são resíduos quadráticos.
• Se ${\displaystyle p\equiv 3{\text{ mod }}4}$ então o fato de que

  ${\displaystyle {\frac {p+1}{4}}+{\frac {p+1}{4}}={\frac {(p-1)+2}{2}}}$ nos dá que ${\displaystyle a=x^{(p+1)/4}}$ é a raiz quadrada do resíduo quadrático ${\displaystyle x}$.

• O símbolo de Legendre é periódico em seu primeiro (ou superior) argumento: se a ≡ b (mod p), então

  ${\displaystyle \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right).}$

• O símbolo de Legendre é uma função completamente multiplicativa de seu argumento principal:

  ${\displaystyle \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 resíduo com um não resíduo é um não resíduo. Um caso especial é o símbolo de Legendre de um quadrado:

  ${\displaystyle \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 ${\displaystyle \left({\frac {a}{p}}\right)}$ é o único caracter de Dirichlet quadrático (ou de ordem 2) módulo p.
• O primeiro suplemento à lei da reciprocidade quadrática:

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

  ${\displaystyle \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 ${\displaystyle \left({\frac {a}{p}}\right)}$ para pequenos valores de a:
  • Para um primo ímpar p ≠ 3

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

    ${\displaystyle \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₁ = F₂ = 1, F_n+1 = F_n + F_n−1. Se p é um número primo, então

  ${\displaystyle F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p}},\qquad F_{p}\equiv \left({\frac {p}{5}}\right){\pmod {p}}.}$

Por exemplo,

${\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 vem da teoria das sequências de Lucas, que são usadas em testes de primalidade.[4] Veja o artigo Primos de Wall–Sun–Sun.

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:

${\displaystyle \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 são baseadas na fórmula de Legendre

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

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

em sua quarta[5] e sexta[6] provas de reciprocidade quadrática.

A prova de Kronecker[7] primeiro estabelece 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).}$

Invertendo as funções de p e q, ele obtém a relação entre (pq) e (qp) Uma das provas de Eisenstein[8] começa mostrando que

${\displaystyle \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 reciprocidade cúbica e quártica também.

• 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 (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 para n = 2.

As propriedades acima, incluindo a lei da reciprocidade quadrática, podem ser usadas para avaliar qualquer símbolo de Legendre. Por exemplo:

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

Ou usando um cálculo mais 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.}$

O artigo 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 eficientes são, em geral, é mais eficiente usar a definição original de Legendre, por exemplo

${\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 o módulo quadrado repetido 331, reduzindo cada valor usando o módulo após cada operação para evitar computação com números inteiros grandes.

• Gauss, Carl Friedrich; Maser, H. (tradutor para alemão) (1965), Estudos em aritmética superior (Investigações aritméticas e outros artigos sobre teoria dos números) (Segunda edição), ISBN 0-8284-0191-8, Nova Iorque: Chelsea
• Gauss, Carl Friedrich; Clarke, Arthur A. (tradutor para o inglês) (1986), Investigações aritméticas (Segunda edição corrigida), ISBN 0-387-96254-9, Nova Iorque: Springer
• Bach, Eric; Shallit, Jeffrey (1996), Teoria algorítmica dos números (volume 1: Algoritmos eficientes), ISBN 0-262-02405-5, Cambridge: MIT Presss
• Hardy, G. H.; Wright, E. M. (1980), Uma introdução à teoria dos números (Quinta edição), ISBN 978-0-19-853171-5, Oxford: Oxford University Press
• Ireland, Kenneth; Rosen, Michael (1990), Uma introdução clássica à teoria dos números moderna (Segunda edição), ISBN 0-387-97329-X, Nova Iorque: Springer
• Lemmermeyer, Franz (2000), Leis de reciprocidade: de Euler a Eisenstein, ISBN 3-540-66957-4, Berlim: Springer
• Ribenboim, Paulo (1996), O novo livro de registros de números primos, ISBN 0-387-94457-5, Nova Iorque: Springer

• Calculadora de símbolo de Jacobi (em inglês)