Símbolo de Legendre

Símbolo de Legendre(Modelo:Sfrac)
para varios a (na parte superior) e p (no lado esquerdo).

Modelo:Diagonal split header	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	Modelo:00	Modelo:01	−1	1	Modelo:01	1	−1	−1	−1	Modelo:01	−1
Só se mostran 0 ≤ a < p, xa que debido á primeira propiedade definida no artigo calquera outra a pódese reducir módulo p. Os residuos cadráticos están resaltados en amarelo e corresponden aos valores 0 e 1.

En teoría de números, o símbolo de Legendre é unha función multiplicativa con valores $\{1,-1,0\}$ que é un carácter cadrático módulo un número primo impar $p$: o seu valor para un residuo cadrático (non cero) $modp$ é $1$ e para un residuo non cadrático (un non residuo) é $-1$. O seu valor en cero é $0$.

O símbolo de Legendre foi introducido por Adrien-Marie Legendre en 1798 no curso dos seus intentos de probar a lei da reciprocidade cadrática. As xeneralizacións do símbolo inclúen o símbolo de Jacobi e os caracteres de Dirichlet de orde superior. A conveniencia de notación do símbolo de Legendre inspirou a introdución doutros "símbolos" usados na teoría alxébrica de números, como o símbolo de Hilbert e o símbolo de Artin.

Definición

Sexa $p$ un número primo impar. Un número enteiro $a$ é un residuo cadrático módulo $p$ se é congruente cun cadrado perfecto módulo $p$ e é non residuo cadrático módulo $p$ no caso contrario. O símbolo de Legendre é unha función de $a$ e $p$ definido como

$\left(\frac{a}{p}\right)=\{\begin{array}{cc}1& \text{se }a\text{ é un residuo cadrático módulo }p\text{ e }a\equiv ̸0(\mathrm{mod}p),\\ -1& \text{se }a\text{ é un non residuo cadrático módulo }p,\\ 0& \text{se }a\equiv 0(\mathrm{mod}p).\end{array}$

A definición orixinal de Legendre foi mediante a 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\}.$

Segundo o criterio de Euler, que fora descuberto antes e que Legendre coñecía, estas dúas definicións son equivalentes. Así, a contribución de Legendre radicaba na introdución dunha notación conveniente que rexistrase residuos cadráticos de a mod p. Para comparar, Gauss utilizou a notación a R p, a N p segundo se a é un residuo ou un non residuo módulo p. Por comodidade tipográfica, o símbolo de Legendre ás veces escríbese como (a | p). Para un p fixo, a secuencia $\left(\frac{0}{p}\right),\left(\frac{1}{p}\right),\left(\frac{2}{p}\right),\dots$ é periódica con período p e ás veces chámase secuencia de Legendre. Cada fila da seguinte táboa presenta periodicidade, tal e como se describe.

Táboa de valores

A seguinte é unha táboa de valores do símbolo de Legendre $\left(\frac{a}{p}\right)$ para p ≤ 127, a ≤ 30, p primo impar.

Modelo:Cabeceira 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	Modelo:01	−1	0	Modelo:01	−1	0	1	−1	Modelo:00	1	−1	0	1	−1	0	Modelo:01	−1	0	1	−1	0	1	−1	0	Modelo: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

Propiedades do símbolo de Legendre

Hai unha serie de propiedades útiles do símbolo de Legendre que, xunto coa lei da reciprocidade cadrática, poden ser usadas para calculalo de forma eficiente.

• Dado un xerador $g\in {𝔽}_p^{*}$, se $x=g^r$, entón $x$ é un residuo cadrático se e só se $r$ é par. Isto mostra que a metade dos elementos en ${𝔽}_p^{*}$ son residuos cadráticos.
• Se $p\equiv 3\text{ mod }4$ entón o feito de que

  $\frac{p+1}{4}+\frac{p+1}{4}=\frac{p+1}{2}=\frac{(p-1)+2}{2}=\frac{p-1}{2}+1$ dános que $a=x^{(p+1)/4}$ é unha raíz cadrada do residuo cadrático $x$.

• O símbolo de Legendre é periódico no seu primeiro argumento (ou superior): se a ≡ b (mod p), entón

  $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right).$

• O símbolo de Legendre é un función multiplicativa do seu argumento superior:

  $\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right).$

• En particular, o produto de dous números que son residuos cadráticos ou non residuos cadráticos módulo p é un residuo, mentres que o produto dun residuo cun non residuo é un non residuo. Un caso especial é o símbolo de Legendre dun cadrado:

  $\left(\frac{x^2}{p}\right)=\{\begin{array}{cc}1& \text{se }p\nmid x\\ 0& \text{se }p\mid x.\end{array}$

• Cando se ve como unha función de a, o símbolo de Legendre $\left(\frac{a}{p}\right)$ é o único carácter de Dirichlet cadrático (ou orde 2) módulo p.
• O primeiro suplemento á lei da reciprocidade cadrática:

  $\left(\frac{-1}{p}\right)=(-1{)}^{\frac{p-1}{2}}=\{\begin{array}{cc}1& \text{ if }p\equiv 1(\mathrm{mod}4)\\ -1& \text{ if }p\equiv 3(\mathrm{mod}4).\end{array}$

• O segundo suplemento á lei da reciprocidade cadrática:

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

• Fórmulas especiais para o símbolo de Legendre $\left(\frac{a}{p}\right)$ para valores pequenos de a:
  • Para un primo impar 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 un primo impar p ≠ 5,

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

• Os números de Fibonacci 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... son definidos pola recorrencia Modelo:Nowrap Modelo:Nowrap Se p é un número primo daquela

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

• Este resultado provén da teoría das secuencias de Lucas, que se usan nos test de primalidade. Consulte primo de Wall–Sun–Sun.

Símbolo de Legendre e reciprocidade cadrática

Sexan p e q números primos impares distintos. Usando o símbolo de Legendre, a lei de reciprocidade cuadrática pódese enunciar concisamente:

$\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1{)}^{\frac{p-1}{2}\cdot \frac{q-1}{2}}.$

Moitas probas da reciprocidade cadrática baséanse no criterio de Euler

$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}(\mathrm{mod}p).$

• Gauss introduciu a suma cadrática de Gauss e utilizou 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}}$

na súa cuarta e sexta probas da reciprocidade cadrática.

Funcións relacionadas

• O símbolo de Jacobi (Modelo:Sfrac) é unha xeneralización do símbolo de Legendre que permite un segundo argumento composto (inferior) n, aínda que n debe ser impar e positivo. Esta xeneralización proporciona un xeito eficiente de calcular todos os símbolos de Legendre sen realizar a factorización.
• Outra extensión é o símbolo de Kronecker, no que o argumento inferior pode ser calquera número enteiro.
• O símbolo do residuo de potencia (Modelo:Sfrac)Modelo:Sub xeneraliza o símbolo de Legendre a unha potencia superior n. O símbolo de Legendre representa o símbolo do residuo de potencia para n = 2.

Exemplo computacional

As propiedades anteriores, incluída a lei da reciprocidade cadrática, pódense usar para avaliar calquera 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 un cálculo máis 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.$

Dado que non se coñece un algoritmo de factorización eficiente, mais os algoritmos de exponenciación modular son eficientes, en xeral, é máis eficiente usar a definición orixinal 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 repetidamente o cadrado módulo 331, reducindo cada valor usando o módulo despois de cada operación para evitar o cálculo con enteiros grandes.

Véxase tamén

Bibliografía

• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro

Outros artigos

• Símbolo de Jacobi.
• Teorema de Dirichlet sobre progresións aritméticas

Ligazóns externas

• calculadora de símbolos de Jacobi