Símbolo de Legendre

Símbolo de Legendre(a/p)
para varios a (na parte superior) e p (no 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
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) $\mod p$ é $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^[1] 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{cases}1&{\text{se }}a{\text{ é un residuo cadrático módulo }}p{\text{ e }}a\not \equiv 0{\pmod {p}},\\-1&{\text{se }}a{\text{ é un non residuo cadrático módulo }}p,\\0&{\text{se }}a\equiv 0{\pmod {p}}.\end{cases}}

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

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({\tfrac {0}{p}}\right),\left({\tfrac {1}{p}}\right),\left({\tfrac {2}{p}}\right),\ldots$ é 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.

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

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 \mathbb {F} _{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 $\mathbb {F} _{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{cases}1&{\mbox{se }}p\nmid x\\0&{\mbox{se }}p\mid x.\end{cases}}$
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{cases}1&{\mbox{ if }}p\equiv 1{\pmod {4}}\\-1&{\mbox{ if }}p\equiv 3{\pmod {4}}.\end{cases}}$
O segundo suplemento á lei da reciprocidade cadrática:
$\left({\frac {2}{p}}\right)=(-1)^{\tfrac {p^{2}-1}{8}}={\begin{cases}1&{\mbox{ if }}p\equiv 1{\mbox{ or }}7{\pmod {8}}\\-1&{\mbox{ if }}p\equiv 3{\mbox{ or }}5{\pmod {8}}.\end{cases}}$
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)^{{\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 un primo impar 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{ ou }}4{\pmod {5}}\\-1&{\mbox{ se }}p\equiv 2{\mbox{ ou }}3{\pmod {5}}.\end{cases}}$
Os números de Fibonacci 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... son definidos pola recorrencia F₁ = F₂ = 1, F_n+1 = F_n + F_n−1. Se p é un número primo daquela
$F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p}},\qquad F_{p}\equiv \left({\frac {p}{5}}\right){\pmod {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)^{{\tfrac {p-1}{2}}\cdot {\tfrac {q-1}{2}}}.

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

\left({\frac {a}{p}}\right)\equiv a^{\tfrac {p-1}{2}}{\pmod {p}}.

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

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

Funcións relacionadas

O símbolo de Jacobi (a/n) é 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 (a/n)_n 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{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 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)^{\tfrac {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{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 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.

Notas

↑ Legendre, A. M. (1798). Essai sur la théorie des nombres. Paris. p. 186.

Véxase tamén

Bibliografía

Gauss, Carl Friedrich (1965). Untersuchungen über höhere Arithmetik (Disquisitiones Arithmeticae & other papers on number theory). Traducido por Maser, H. (Second ed.). New York: Chelsea. ISBN 0-8284-0191-8.
Gauss, Carl Friedrich (1986). Disquisitiones Arithmeticae. Traducido por Clarke, Arthur A. (Second, corrected ed.). New York: Springer. ISBN 0-387-96254-9.
Bach, Eric; Shallit, Jeffrey (1996). Algorithmic Number Theory. I: Efficient Algorithms). Cambridge: The MIT Press. ISBN 0-262-02405-5.
Hardy, G. H.; Wright, E. M. (1980). An Introduction to the Theory of Numbers (Fifth edition). Oxford: Oxford University Press. ISBN 978-0-19-853171-5.
Ireland, Kenneth; Rosen, Michael (1990). A Classical Introduction to Modern Number Theory (Second ed.). New York: Springer. ISBN 0-387-97329-X.
Lemmermeyer, Franz (2000). Reciprocity Laws: from Euler to Einstein. Berlin: Springer. ISBN 3-540-66957-4.
Ribenboim, Paulo (1996). The New Book of Prime Number Records. New York: Springer. ISBN 0-387-94457-5.

Outros artigos

Ligazóns externas

calculadora de símbolos de Jacobi

[1] Legendre, A. M. (1798). Essai sur la théorie des nombres. Paris. p. 186.

[1]