+ Símbolo de Legendre () para vários a (ao longo do topo) e p (ao longo do lado esquerdo). 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 −1Apenas 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 e o símbolo de Artin.
Definição
Seja um número primo ímpar. Um inteiro é um resíduo quadrático módulo se for congruente a um quadrado perfeito módulo e ,caso não, é um não resíduo quadrático módulo . O símbolo de Legendre é uma função de e definida como
A definição original de Legendre era por meio da fórmula explícita
Pelo Critério de Euler, que foi descoberto anteriormente e era conhecido por Legendre, essas duas definições são equivalentes.Hardy & Wright, Thm. 83. 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 é periódica 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 com p ≤ 127, a ≤ 30, p primo ímpar.
12345678910111213141516171819202122232425262728293031−101−101−101−101−101−101−101−101−101−1051−1−1101−1−1101−1−1101−1−1101−1−1101−1−110711−11−1−1011−11−1−1011−11−1−1011−11−1−1011111−1111−1−1−11−101−1111−1−1−11−101−1111−1−1−1131−111−1−1−1−111−1101−111−1−1−1−111−1101−1111711−11−1−1−111−1−1−11−111011−11−1−1−111−1−1−11191−1−11111−11−11−1−1−1−111−101−1−11111−11−11231111−11−111−1−111−1−11−11−1−1−1−101111−11−1291−1−11111−11−1−1−11−1−11−1−1−11−11111−1−11013111−111−11111−1−1−11−11−1111−1−1−1−11−1−11−1−1371−111−1−11−11111−1−1−11−1−1−1−11−1−1−11111−114111−111−1−1111−1−1−1−1−11−11−111−11−11−1−1−1−1−1431−1−11−11−1−1111−111111−1−1−11−1111−1−1−1−1−1471111−11111−1−11−11−1111−1−11−1−111−111−1−1531−1−11−111−1111−11−1111−1−1−1−1−1−111−1−111−1591−1111−11−11−1−11−1−1111−11111−1−111111−1611−1111−1−1−11−1−111111−1−111−11−1−11−11−1−1−1671−1−11−11−1−111−1−1−11111−11−1111111−1−11−171111111−1111−11−1−111−1111−1−1−111−11−111731111−11−111−1−11−1−1−11−111−1−1−1111−11−1−1−17911−111−1−11111−11−1−11−1111111−111−1−1−1−1831−111−1−11−11111−1−1−111−1−1−11−11−11111118911−111−1−11111−1−1−1−1111−1111−1−11−1−1−1−1−1971111−11−111−111−1−1−11−11−1−1−11−111−11−1−1−11011−1−1111−1−11−1−1−111−111−11111111−1−1−1−1110311−11−1−1111−1−1−11111111−1−1−11−111−11111071−111−1−1−1−1111111−11−1−11−1−1−11−11−11−1111091−1111−11−11−1−11−1−111−1−1−1111−1−111111−111311−11−1−1111−11−11111−11−1−1−11−1−111−11−1112711−11−1−1−111−11−11−111111−111−1−111−1−1−11
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 , se , então é um resíduo quadrático se e somente se for par. Isso também mostra que metade dos elementos diferentes de zero em são resíduos quadráticos.
Se então o fato de que nos dá que é a raiz quadrada do resíduo quadrático .
O símbolo de Legendre é periódico em seu primeiro (ou superior) argumento: se a ≡ b (mod p), então
O símbolo de Legendre é uma função completamente multiplicativa de seu argumento principal:
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:
Quando visto como uma função de a, o símbolo de Legendre é o único caráter de Dirichlet quadrático (ou de ordem 2) módulo p.
O primeiro suplemento à lei da reciprocidade quadrática:
O segundo suplemento à lei da reciprocidade quadrática:
Fórmulas especiais para o símbolo de Legendre para pequenos valores de a: Para um primo ímpar p ≠ 3
Para um primo ímpar p ≠ 5,
Os números de Fibonacci 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … são definidos pela recorrência Se p é um número primo, então
Por exemplo,
Este resultado vem da teoria das sequências de Lucas, que são usadas em testes de primalidade.Ribenboim, p. 64; Lemmermeyer, ex. 2.25–2.28, pp. 73–74. 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:
Muitas provas de reciprocidade quadrática são baseadas no Critério de Euler
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
em sua quartaGauss, "Summierung gewisser reihen von besonderer art" (1811), reimpresso em Untersuchungen ... pp. 463–495 e sextaGauss, "Neue beweise und erweiterungen des fundamentalsatzes in der lehre von den quadratischen resten" (1818) reimpresso em Untersuchungen ... pp. 501–505 provas de reciprocidade quadrática.
A prova de KroneckerLemmermeyer, ex. p. 31, 1.34 primeiro estabelece que
Invertendo as funções de p e q, ele obtém a relação entre () e ()
Uma das provas de EisensteinLemmermeyer, pp. 236 ff. começa mostrando que
Usando certas funções elípticas em vez da função seno, Eisenstein foi capaz de provar as reciprocidades cúbica e quártica também.
Funções relacionadas
O símbolo de Jacobi () é 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 () 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.
Exemplo computacional
As propriedades acima, incluindo a lei da reciprocidade quadrática, podem ser usadas para avaliar qualquer símbolo de Legendre. Por exemplo:
Ou usando um cálculo mais eficiente:
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 eficientes são, em geral, é mais eficiente usar a definição original de Legendre, por exemplo
usando quadratura repetida módulo 331, reduzindo cada valor usando o módulo após cada operação para evitar computação com números inteiros grandes.
Notas
Referências
Ligações externas
Calculadora de símbolo de Jacobi (em inglês)
Categoria:Aritmética modular Categoria:Resíduo quadrático