Mostrar código-fonte de Símbolo de Legendre

{{Descrição curta|Função multiplicativa com valores 1, −1, 0}}

{| class="wikitable floatright" style="width:220px; text-align:right;"
|+ Símbolo de Legendre ({{sfrac|''a''|''p''}})<br/>
para vários ''a'' (ao longo do topo) e ''p'' (ao longo do lado esquerdo). 
! {{Cabeçalho de divisão diagonal|''p'' | ''a''}} !! 0 !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7 !! 8 !! 9 !! 10
|-
! 3
|style="background:#fafa6a"| 0
|style="background:#fafa6a"| 1 || −1 || || || || || || || || 
|-
! 5
|style="background:#fafa6a"| 0
|style="background:#fafa6a"| 1 || −1 || −1
|style="background:#fafa6a"| 1 || || || || || || 
|-
! 7
|style="background:#fafa6a"| 0
|style="background:#fafa6a"| 1
|style="background:#fafa6a"| 1 || −1
|style="background:#fafa6a"| 1 || −1 || −1 || || || || 
|-
! 11
|style="background:#fafa6a"| {{0|−}}0
|style="background:#fafa6a"| {{0|−}}1 || −1
|style="background:#fafa6a"| 1
|style="background:#fafa6a"| {{0|−}}1
|style="background:#fafa6a"| 1 || −1 || −1 || −1
|style="background:#fafa6a"| {{0|−}}1 || −1
|-
|colspan="12" class="thumbcaption"|
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íduo quadrático|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 [[Operação módulo|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,<ref>{{Cite book |first=A. M. |last=Legendre |title=Essai sur la théorie des nombres |url=https://archive.org/details/essaisurlathor00lege |location=Paris |year=1798 |page=[https://archive.org/details/essaisurlathor00lege/page/186 186] }}</ref>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 [[Caráter de Dirichlet|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{{Ill|en||Hilbert symbol|nlk=true}} e o símbolo de Artin{{Ill|en||Artin reciprocity law|nlk=true}}.

==Definição==

Seja <math>p</math> um número primo ímpar. Um inteiro <math>a</math> é um resíduo quadrático módulo <math>p</math> se for congruente a um quadrado perfeito módulo <math>p</math> e ,caso não, é um não resíduo quadrático módulo <math>p</math>. O símbolo de Legendre é uma função de <math>a</math> e <math>p</math> definida como
:<math>\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}</math>

A definição original de Legendre era por meio da fórmula explícita
:<math> \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\}. </math>

Pelo [[Critério de Euler]], que foi descoberto anteriormente e era conhecido por Legendre, essas duas definições são equivalentes.<ref>Hardy & Wright, Thm. 83.</ref> 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, [[Carl Friedrich Gauss|Gauss]] usou a notação ''a''R''p'', ''a''N''p'' 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 <math>\left(\tfrac{0}{p}\right),\left(\tfrac{1}{p}\right),\left(\tfrac{2}{p}\right),\ldots</math> é periódica{{Ill|en||Periodic sequence|nlk=true}} 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 <math>\left(\frac{a}{p}\right)</math> com ''p'' ≤ 127, ''a'' ≤ 30, ''p'' primo ímpar.

{|class="wikitable" style="text-align:right;"
!{{cabeçalho de divisão diagonal|''p''|''a''}}
!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
|style="background:#ffccff"|{{0|−}}1
|style="background:#ccffff"|−1
|style="background:#ffffcc"|0
|style="background:#ffccff"|{{0|−}}1
|style="background:#ccffff"|−1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffffcc"|{{0|−}}0
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffffcc"|0
|style="background:#ffccff"|{{0|−}}1
|style="background:#ccffff"|−1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffffcc"|0
|style="background:#ffccff"|{{0|−}}1
|style="background:#ccffff"|−1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffffcc"|0
|-
!5
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffffcc"|0
|-
!7
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|-
!11
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|-
!13
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|-
!17
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|-
!19
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|-
!23
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|-
!29
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffffcc"|0
|style="background:#ffccff"|1
|-
!31
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|-
!37
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|-
!41
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|-
!43
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|-
!47
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|-
!53
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|-
!59
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|-
!61
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|-
!67
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|-
!71
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|-
!73
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|-
!79
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|-
!83
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|-
!89
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|-
!97
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|-
!101
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|-
!103
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|-
!107
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|-
!109
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|-
!113
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|-
!127
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|1
|style="background:#ffccff"|1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ccffff"|−1
|style="background:#ffccff"|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 <math>g \in \mathbb{F}_p^*</math>, se <math>x = g^r</math>, então <math>x</math> é um resíduo quadrático se e somente se <math>r</math> for par. Isso também mostra que metade dos elementos diferentes de zero em <math>\mathbb{F}_p^*</math> são resíduos quadráticos.

* Se <math>p \equiv 3 \text{ mod } 4</math> então o fato de que
*:<math> \frac{p+1}{4} + \frac{p+1}{4} = \frac{(p-1)+2}{2}</math> nos dá que <math>a = x^{(p+1)/4}</math> é a [[raiz quadrada]] do resíduo quadrático <math>x</math>.

* O símbolo de Legendre é periódico em seu primeiro (ou superior) argumento: se ''a'' ≡ ''b'' (mod ''p''), então
*:<math> \left(\frac{a}{p}\right) = \left(\frac{b}{p}\right).</math>

* O símbolo de Legendre é uma [[função completamente multiplicativa]] de seu argumento principal:
*:<math>\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right).</math>

* 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:
*:<math>\left(\frac{x^2}{p}\right) = \begin{cases} 1 & \mbox{se }p\nmid x\\ 0 & \mbox{se }p\mid x. \end{cases}</math>

* Quando visto como uma função de ''a'', o símbolo de Legendre <math>\left(\frac{a}{p}\right) </math> é o único [[Caráter de Dirichlet|caráter de Dirichlet]] quadrático (ou de ordem 2) módulo ''p''.

* O primeiro suplemento à lei da reciprocidade quadrática:
*:<math>\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}</math>

* O segundo suplemento à lei da reciprocidade quadrática:
*:<math> \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}</math>

* Fórmulas especiais para o símbolo de Legendre <math>\left(\frac{a}{p}\right) </math> para pequenos valores de ''a'':
**Para um primo ímpar ''p'' ≠ 3
**:<math> \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}</math>
** Para um primo ímpar ''p'' ≠ 5,  
**:<math> \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 \pmod5 \\
    -1 & \mbox{ se }p \equiv 2\mbox{ or }3 \pmod5.
  \end{cases}</math>

* Os [[Sequência de Fibonacci|números de Fibonacci]] 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … são definidos pela recorrência {{Nowrap|''F''<sub>1</sub> {{=}} ''F''<sub>2</sub> {{=}} 1,}} {{Nowrap|''F''<sub>''n''+1</sub> {{=}} ''F<sub>n</sub>'' + ''F''<sub>''n''−1</sub>.}} Se ''p'' é um número primo, então
*:<math> F_{p-\left(\frac{p}{5}\right)} \equiv 0 \pmod p, \qquad F_{p} \equiv \left(\frac{p}{5}\right) \pmod p. </math> 
:Por exemplo, 
::<math>\begin{align}
    \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{align}</math> 

* Este resultado vem da teoria das [[Sequência de Lucas|sequências de Lucas]], que são usadas em [[Teste de primalidade|testes de primalidade]].<ref>Ribenboim, p. 64; Lemmermeyer, ex. 2.25–2.28, pp. 73–74.</ref> 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:
: <math>\left(\frac{q}{p}\right)\left(\frac{p}{q}\right) = (-1)^{\tfrac{p-1}{2}\cdot\tfrac{q-1}{2}}.</math>

Muitas provas de reciprocidade quadrática{{Ill|en||Proofs of quadratic reciprocity|nlk=true}} são baseadas no Critério de Euler
:<math>\left(\frac{a}{p}\right) \equiv a^{\tfrac{p-1}{2}} \pmod p.</math>

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
::<math>\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}}</math>
:em sua quarta<ref>Gauss, "''Summierung gewisser reihen von besonderer art''" (1811), reimpresso em ''Untersuchungen ...'' pp. 463–495</ref> e sexta<ref>Gauss, "''Neue beweise und erweiterungen des fundamentalsatzes in der lehre von den quadratischen resten''" (1818) reimpresso em ''Untersuchungen ...'' pp. 501–505</ref> provas de reciprocidade quadrática.

A prova de [[Leopold Kronecker|Kronecker]]<ref>Lemmermeyer, ex. p. 31, 1.34</ref> primeiro estabelece que
::<math>\left(\frac{p}{q}\right) =\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).</math>

Invertendo as funções de ''p'' e ''q'', ele obtém a relação entre ({{Sfrac|''p''|''q''}}) e ({{Sfrac|''q''|''p''}})

Uma das provas de [[Gotthold Eisenstein|Eisenstein]]<ref>Lemmermeyer, pp. 236 ff.</ref> começa mostrando que
::<math>\left(\frac{q}{p}\right) =\prod_{n=1}^{\frac{p-1}{2}} \frac{\sen\left(\frac{2\pi qn}{p}\right)}{\sen\left(\frac{2\pi n}{p}\right)}.</math>

Usando certas [[Função elíptica|funções elípticas]] em vez da [[Seno|função seno]], Eisenstein foi capaz de provar as reciprocidades cúbica{{Ill|en||Cubic reciprocity|nlk=true}} e quártica{{Ill|en||Quartic reciprocity|nlk=true}} também.

== Funções relacionadas ==

* O [[símbolo de Jacobi]] ({{Sfrac|''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{{Ill|en||Power residue symbol|nlk=true}} ({{Sfrac|''a''|''n''}}){{Subscrito|''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{{Ill|en||Power residue symbol|nlk=true}} 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:
:<math>\begin{align}
\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{align}</math>

Ou usando um cálculo mais eficiente:
:<math>\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.</math>

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 de inteiros|fatoração]] eficiente é conhecido, mas algoritmos de [[exponenciação]] modular{{Ill|en||Modular exponentiation|nlk=true}} eficientes são, em geral, é mais eficiente usar a definição original de Legendre, por exemplo
:<math>\begin{align}
\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{align}</math>

usando quadratura repetida{{Ill|en||Exponentiation by squaring|nlk=true}} 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 ==
{{Reflist|30em}}

== Referências ==

* {{Citation |last=Gauss |first=Carl Friedrich |author-link=Carl Friedrich Gauss |translator-last=Maser |translator-first=H. |title=Untersuchungen über höhere arithmetik (Disquisitiones arithmeticae & other papers on number theory) |edition=2ª |publisher=''Chelsea'' |location=New York |year=1965 |isbn=0-8284-0191-8 }}
* {{Citation |last=Gauss |first=Carl Friedrich |author-link=Carl Friedrich Gauss |translator-last=Clarke |translator-first=Arthur A. |title=Disquisitiones arithmeticae |edition=2ª, corrigida |publisher=[[Springer Science+Business Media|''Springer'']] |location=New York |year=1986 |isbn=0-387-96254-9 }}
* {{Citation |last1=Bach |first1=Eric |last2=Shallit |first2=Jeffrey |title=Algorithmic number theory |volume=I: Efficient algorithms |publisher=<!-- [[:en:The MIT Press]] -->''The M.I.T. Press'' |location=Cambridge |year=1996 |isbn=0-262-02405-5 }}
* {{Citation |last1=Hardy |first1=G. H. |author-link1=G. H. Hardy |last2=Wright |first2=E. M. |title=An introduction to the theory of numbers |edition=5ª |publisher=[[Oxford University Press]] |location=Oxford |year=1980 |isbn=978-0-19-853171-5 |url-access=registro |url=https://archive.org/details/introductiontoth00hard }}
* {{Citation |last1=Ireland |first1=Kenneth |last2=Rosen |first2=Michael |title=A classical introduction to modern number theory |edition=2ª |publisher=[[Springer Science+Business Media|''Springer'']] |location=New York |year=1990 |isbn=0-387-97329-X }}
* {{Citation |last1=Lemmermeyer |first1=Franz |title=Reciprocity laws: from Euler to Eisenstein |publisher=[[Springer Science+Business Media|''Springer'']] |location=Berlin |year=2000 |isbn=3-540-66957-4 }}
* {{Citation |last1=Ribenboim |first1=Paulo |title=The new book of prime number records |publisher=[[Springer Science+Business Media|''Springer'']] |location=New York |year=1996 |isbn=0-387-94457-5 }}

== Ligações externas ==

* [http://math.fau.edu/richman/jacobi.htm Calculadora de símbolo de Jacobi] (em inglês)

[[Categoria:Aritmética modular]]
[[Categoria:Resíduo quadrático]]