Símbolo de Legendre

Símbolo de Legendre (⁠a/p⁠)
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].

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.^[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 $\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.

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

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)$ $\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₁ = F₂ = 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.^[3] 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^[4] e sexta^[5] provas de reciprocidade quadrática.

A prova de Kronecker^[6] 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 (⁠p/q⁠) e (⁠q/p⁠)

Uma das provas de Eisenstein^[7] 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 (⁠a/n⁠) é 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] (⁠a/n⁠)_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.

Notas

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

Referências

Gauss, Carl Friedrich (1965), Untersuchungen über höhere arithmetik (Disquisitiones arithmeticae & other papers on number theory), ISBN 0-8284-0191-8, traduzido por Maser, H. 2ª ed. , New York: Chelsea
Gauss, Carl Friedrich (1986), Disquisitiones arithmeticae, ISBN 0-387-96254-9, traduzido por Clarke, Arthur A. 2ª, corrigida ed. , New York: Springer
Bach, Eric; Shallit, Jeffrey (1996), Algorithmic number theory, ISBN 0-262-02405-5, I: Efficient algorithms, Cambridge: The M.I.T. Press
Hardy, G. H.; Wright, E. M. (1980), An introduction to the theory of numbers, ISBN 978-0-19-853171-5 5ª ed. , Oxford: Oxford University Press
Ireland, Kenneth; Rosen, Michael (1990), A classical introduction to modern number theory, ISBN 0-387-97329-X 2ª ed. , New York: Springer
Lemmermeyer, Franz (2000), Reciprocity laws: from Euler to Eisenstein, ISBN 3-540-66957-4, Berlin: Springer
Ribenboim, Paulo (1996), The new book of prime number records, ISBN 0-387-94457-5, New York: Springer

Ligações externas

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]