Símbolo de Legendre

Símbolo de Legendre (Predefinição:Sfrac)
para vários a (ao longo do topo) e p (ao longo do lado esquerdo).

Predefinição:Cabeçalho de divisão diagonal	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	Predefinição:00	Predefinição:01	−1	1	Predefinição:01	1	−1	−1	−1	Predefinição:01	−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 HilbertPredefinição:Ill e o símbolo de ArtinPredefinição:Ill.

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{array}{cc}1& \text{se }a\text{ é um resíduo quadrático modulo }p\text{ e }a\equiv ̸0(\mathrm{mod}p),\\ -1& \text{se }a\text{ é um não resíduo quadrático modulo }p,\\ 0& \text{se }a\equiv 0(\mathrm{mod}p).\end{array}$

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}}(\mathrm{mod}p)\text{ e }\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(\frac{0}{p}\right),\left(\frac{1}{p}\right),\left(\frac{2}{p}\right),\dots$ é periódicaPredefinição:Ill 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.

Predefinição:Cabeçalho de divisão diagonal	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	Predefinição:01	−1	0	Predefinição:01	−1	0	1	−1	Predefinição:00	1	−1	0	1	−1	0	Predefinição:01	−1	0	1	−1	0	1	−1	0	Predefinição:01	−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 {𝔽}_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 ${𝔽}_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{array}{cc}1& \text{se }p\nmid x\\ 0& \text{se }p\mid x.\end{array}$

• 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{array}{cc}1& \text{ se }p\equiv 1(\mathrm{mod}4)\\ -1& \text{ se }p\equiv 3(\mathrm{mod}4).\end{array}$

• O segundo suplemento à lei da reciprocidade quadrática:

  $\left(\frac{2}{p}\right)=(-1{)}^{\frac{p^2-1}{8}}=\{\begin{array}{cc}1& \text{ se }p\equiv 1\text{ ou }7(\mathrm{mod}8)\\ -1& \text{ se }p\equiv 3\text{ ou }5(\mathrm{mod}8).\end{array}$

• 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{)}^{\lfloor \frac{p+1}{6}\rfloor }=\{\begin{array}{cc}1& \text{ se }p\equiv 1\text{ ou }11(\mathrm{mod}12)\\ -1& \text{ se }p\equiv 5\text{ ou }7(\mathrm{mod}12).\end{array}$

  • Para um primo ímpar p ≠ 5,

    $\left(\frac{5}{p}\right)=(-1{)}^{\lfloor \frac{2p+2}{5}\rfloor }=\{\begin{array}{cc}1& \text{ se }p\equiv 1\text{ or }4(\mathrm{mod}5)\\ -1& \text{ se }p\equiv 2\text{ or }3(\mathrm{mod}5).\end{array}$

• Os números de Fibonacci 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … são definidos pela recorrência Predefinição:Nowrap Predefinição:Nowrap Se p é um número primo, então

  $F_{p-\left(\frac{p}{5}\right)}\equiv 0(\mathrm{mod}p),F_p\equiv \left(\frac{p}{5}\right)(\mathrm{mod}p).$

Por exemplo,

$\begin{array}{cccccc}\left(\frac{2}{5}\right)& =-1,& F_3& =2,& F_2& =1,\\ \left(\frac{3}{5}\right)& =-1,& F_4& =3,& F_3& =2,\\ \left(\frac{5}{5}\right)& =0,& F_5& =5,& & \\ \left(\frac{7}{5}\right)& =-1,& F_8& =21,& F_7& =13,\\ \left(\frac{11}{5}\right)& =1,& F_{10}& =55,& F_{11}& =89.\end{array}$

• 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{)}^{\frac{p-1}{2}\cdot \frac{q-1}{2}}.$

Muitas provas de reciprocidade quadráticaPredefinição:Ill são baseadas no Critério de Euler

$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}(\mathrm{mod}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 }^{a{k}^2}=\left(\frac{a}{p}\right)\sum _{k=0}^{p-1}{\zeta }^{k^2},\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)=\mathrm{sgn}\left(\prod _{i=1}^{\frac{q-1}{2}}\prod _{k=1}^{\frac{p-1}{2}}(\frac{k}{p}-\frac{i}{q})\right).$

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

Uma das provas de Eisenstein começa mostrando que

$\left(\frac{q}{p}\right)=\prod _{n=1}^{\frac{p-1}{2}}\frac{\mathrm{sen}\left(\frac{2\pi qn}{p}\right)}{\mathrm{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úbicaPredefinição:Ill e quárticaPredefinição:Ill também.

Funções relacionadas

• O símbolo de Jacobi (Predefinição:Sfrac) é 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ênciaPredefinição:Ill (Predefinição:Sfrac)Predefinição:Subscrito 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ênciaPredefinição:Ill 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{array}{cc}\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{array}$

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{)}^{\frac{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 modularPredefinição:Ill eficientes são, em geral, é mais eficiente usar a definição original de Legendre, por exemplo

$\begin{array}{ccc}\left(\frac{98}{331}\right)& \equiv 98^{\frac{331-1}{2}}& (\mathrm{mod}331)\\ & \equiv 98^{165}& (\mathrm{mod}331)\\ & \equiv 98\cdot (98^2{)}^{82}& (\mathrm{mod}331)\\ & \equiv 98\cdot 5^{82}& (\mathrm{mod}331)\\ & \equiv 98\cdot 25^{41}& (\mathrm{mod}331)\\ & \equiv 133\cdot 25^{40}& (\mathrm{mod}331)\\ & \equiv 133\cdot 294^{20}& (\mathrm{mod}331)\\ & \equiv 133\cdot 45^{10}& (\mathrm{mod}331)\\ & \equiv 133\cdot 39^5& (\mathrm{mod}331)\\ & \equiv 222\cdot 39^4& (\mathrm{mod}331)\\ & \equiv 222\cdot 197^2& (\mathrm{mod}331)\\ & \equiv 222\cdot 82& (\mathrm{mod}331)\\ & \equiv -1& (\mathrm{mod}331)\end{array}$

usando quadratura repetidaPredefinição:Ill módulo 331, reduzindo cada valor usando o módulo após cada operação para evitar computação com números inteiros grandes.

Referências

• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Citation

Ligações externas

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