a pag | 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 |
Solo se muestran 0 ≤ a < p , ya que debido a la primera propiedad debajo de cualquier otra a se puede reducir módulo p . Los residuos cuadráticos están resaltados en amarillo y corresponden precisamente a los valores 0 y 1. |
En teoría de números , el símbolo de Legendre es una función multiplicativa con valores 1, -1, 0 que es un carácter cuadrático módulo un número primo impar p : su valor en un residuo cuadrático (distinto de cero) mod p es 1 y en un módulo no cuadrático residuo ( no residuo ) es -1. Su valor en cero es 0.
El símbolo de Legendre fue introducido por Adrien-Marie Legendre en 1798 [1] en el curso de sus intentos de probar la ley de la reciprocidad cuadrática . Las generalizaciones del símbolo incluyen el símbolo de Jacobi y los caracteres de Dirichlet de orden superior. La conveniencia de notación del símbolo de Legendre inspiró la introducción de varios otros "símbolos" utilizados en la teoría de números algebraica , como el símbolo de Hilbert y el símbolo de Artin .
Definición
Dejar ser un número primo impar . Un enteroes un módulo de residuo cuadráticosi es congruente con un módulo cuadrado perfecto y es un módulo cuadrático de no residuos de lo contrario. El símbolo de Legendre es una función de y definido como
La definición original de Legendre fue por medio de la fórmula explícita
Según el criterio de Euler , que se había descubierto antes y que Legendre conocía, estas dos definiciones son equivalentes. [2] Así, la contribución de Legendre radica en introducir una notación conveniente que registra la residuosidad cuadrática de un mod p . En aras de la comparación, Gauss utilizó la notación a R p , a N p según si a es un residuo o un módulo p sin residuo . Por conveniencia tipográfica, el símbolo de Legendre a veces se escribe como ( a | p ) o ( a / p ). La secuencia ( a | p ) para a igual a 0, 1, 2, ... es periódica con el período py a veces se denomina secuencia de Legendre , con valores {0,1, −1} ocasionalmente reemplazados por {1,0 , 1} o {0,1,0}. [3] Se puede ver que cada fila en la siguiente tabla exhibe periodicidad, tal como se describe.
Tabla de valores
La siguiente es una tabla de valores del símbolo de Legendre con p ≤ 127, a ≤ 30, p primo impar.
a pag | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | dieciséis | 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 del símbolo de Legendre
Hay una serie de propiedades útiles del símbolo de Legendre que, junto con la ley de reciprocidad cuadrática , se pueden utilizar para calcularlo de manera eficiente.
- El símbolo de Legendre revela la paridad de un entero distinto de cero mod p. Es decir, dado un generador, Si luego es un residuo cuadrático si y solo si incluso. Esto también muestra que la mitad de los elementos distintos de cero en son residuos cuadráticos.
- Si entonces el hecho de que
- nos da eso es la raíz cuadrada del residuo cuadrático .
- El símbolo de Legendre es periódico en su primer argumento (o superior): si a ≡ b (mod p ), entonces
- El símbolo de Legendre es una función completamente multiplicativa de su argumento superior:
- En particular, el producto de dos números que son residuos cuadráticos o no residuos cuadráticos módulo p es un residuo, mientras que el producto de un residuo con un no residuo es un no residuo. Un caso especial es el símbolo de Legendre de un cuadrado:
- Cuando se ve como una función de a , el símbolo de Legendrees el carácter de Dirichlet cuadrático único (o de orden 2) módulo p .
- El primer complemento a la ley de reciprocidad cuadrática:
- El segundo suplemento a la ley de reciprocidad cuadrática:
- Fórmulas especiales para el símbolo de Legendre para valores pequeños de a :
- Para un primo impar p ≠ 3,
- Para un primo impar p ≠ 5,
- Para un primo impar p ≠ 3,
- Los números de Fibonacci 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,… están definidos por la recurrencia F 1 = F 2 = 1, F n +1 = F n + F n −1 . Si p es un número primo, entonces
- Por ejemplo,
- Este resultado proviene de la teoría de las secuencias de Lucas , que se utilizan en las pruebas de primalidad . [4] Ver Muro-Sol-Sol prima .
Símbolo de Legendre y reciprocidad cuadrática
Deje que p y q sean primos impares distintos. Usando el símbolo de Legendre, la ley de reciprocidad cuadrática se puede enunciar de manera concisa:
Muchas pruebas de reciprocidad cuadrática se basan en la fórmula de Legendre
Además, se idearon varias expresiones alternativas para el símbolo de Legendre con el fin de producir varias pruebas de la ley de reciprocidad cuadrática.
- Gauss introdujo la suma cuadrática de Gauss y usó la fórmula
- La prueba de Kronecker [7] primero establece que
- La inversión de los papeles de p y q , se obtiene la relación entre ( pag/q) y ( q/pag).
- Una de las pruebas de Eisenstein [8] comienza mostrando que
- Usando ciertas funciones elípticas en lugar de la función seno , Eisenstein pudo probar la reciprocidad cúbica y cuártica también.
Funciones relacionadas
- El símbolo de Jacobi ( a/norte) es una generalización del símbolo de Legendre que permite un segundo argumento compuesto (inferior) n , aunque n aún debe ser impar y positivo. Esta generalización proporciona una forma eficiente de calcular todos los símbolos de Legendre sin realizar la factorización en el camino.
- Una extensión adicional es el símbolo Kronecker , en el que el argumento inferior puede ser cualquier número entero.
- El símbolo de residuo de energía ( a/norte) n generaliza el símbolo de Legendre a una potencia superior n . El símbolo de Legendre representa el símbolo de residuo de potencia para n = 2.
Ejemplo computacional
Las propiedades anteriores, incluida la ley de reciprocidad cuadrática, se pueden utilizar para evaluar cualquier símbolo de Legendre. Por ejemplo:
O usando un cálculo más eficiente:
El artículo Símbolo de Jacobi tiene más ejemplos de manipulación de símbolos de Legendre.
Notas
- ↑ Legendre, AM (1798). Essai sur la théorie des nombres . París. pag. 186 .
- ^ Hardy y Wright, Thm. 83.
- ^ Kim, Jeong-Heon; Song, Hong-Yeop (2001). "Representación de trazas de secuencias de Legendre". Diseños, Códigos y Criptografía . 24 : 343–348.
- ^ Ribenboim, pág. 64; Lemmermeyer, ex. 2.25–2.28, págs. 73–74.
- ↑ Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reimpreso en Untersuchungen ... págs. 463–495
- ↑ Gauss, "Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den quadratischen Resten" (1818) reimpreso en Untersuchungen ... pp. 501–505
- ^ Lemmermeyer, ej. pag. 31, 1,34
- ^ Lemmermeyer, págs. 236 y sigs.
Referencias
- Gauss, Carl Friedrich; Maser, H. (traductor al alemán) (1965), Untersuchungen über höhere Arithmetik (Disquisitiones Arithmeticae y otros artículos sobre teoría de números) (segunda edición) , Nueva York: Chelsea, ISBN 0-8284-0191-8
- Gauss, Carl Friedrich; Clarke, Arthur A. (traductor al inglés) (1986), Disquisitiones Arithmeticae (Segunda edición corregida) , Nueva York: Springer , ISBN 0-387-96254-9
- Bach, Eric; Shallit, Jeffrey (1996), Teoría algorítmica de números (Vol I: Algoritmos eficientes) , Cambridge: The MIT Press , ISBN 0-262-02405-5
- Hardy, GH ; Wright, EM (1980), Introducción a la teoría de los números (quinta edición) , Oxford: Oxford University Press , ISBN 978-0-19-853171-5
- Irlanda, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (Segunda edición) , Nueva York: Springer , ISBN 0-387-97329-X
- Lemmermeyer, Franz (2000), Leyes de reciprocidad: de Euler a Eisenstein , Berlín: Springer , ISBN 3-540-66957-4
- Ribenboim, Paulo (1996), The New Book of Prime Number Records , Nueva York: Springer , ISBN 0-387-94457-5
enlaces externos
- Calculadora de símbolos jacobi