Saltar para o conteúdo

Símbolo de Legendre

Origem: Wikipédia, a enciclopédia livre.
Símbolo de Legendre (ap)
para vários a (ao longo do topo) e p (ao longo do lado esquerdo).
a
p
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,[1]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].

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.[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). Para p fixo, a sequência é 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

[editar | editar código-fonte]

A seguir está uma tabela de valores do símbolo de Legendre com p ≤ 127, a ≤ 30, p primo ímpar.

a
p
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

[editar | editar código-fonte]

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 ab (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 F1 = F2 = 1, Fn+1 = Fn + Fn−1. Se p é um número primo, então
Por exemplo,

Símbolo de Legendre e reciprocidade quadrática

[editar | editar código-fonte]

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 [en] 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.

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

A prova de Kronecker[6] primeiro estabelece que

Invertendo as funções de p e q, ele obtém a relação entre (pq) e (qp)

Uma das provas de Eisenstein[7] 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 [en] e quártica [en] também.

Funções relacionadas

[editar | editar código-fonte]
  • 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

[editar | editar código-fonte]

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

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.

  1. Legendre, A. M. (1798). Essai sur la théorie des nombres. Paris: [s.n.] p. 186 
  2. Hardy & Wright, Thm. 83.
  3. Ribenboim, p. 64; Lemmermeyer, ex. 2.25–2.28, pp. 73–74.
  4. Gauss, "Summierung gewisser reihen von besonderer art" (1811), reimpresso em Untersuchungen ... pp. 463–495
  5. Gauss, "Neue beweise und erweiterungen des fundamentalsatzes in der lehre von den quadratischen resten" (1818) reimpresso em Untersuchungen ... pp. 501–505
  6. Lemmermeyer, ex. p. 31, 1.34
  7. Lemmermeyer, pp. 236 ff.

Ligações externas

[editar | editar código-fonte]