En teoría de números , el lema de Zolotarev establece que el símbolo de Legendre
para un entero, un módulo, un número primo impar p , donde p no divide a , se puede calcular como el signo de una permutación:
donde ε denota la firma de una permutación y π a es la permutación de las clases de residuos distintos de cero mod p inducida por la multiplicación por a .
Por ejemplo, tome a = 2 yp = 7. Los cuadrados distintos de cero mod 7 son 1, 2 y 4, entonces (2 | 7) = 1 y (6 | 7) = −1. La multiplicación por 2 en los números distintos de cero mod 7 tiene la descomposición cíclica (1,2,4) (3,6,5), por lo que el signo de esta permutación es 1, que es (2 | 7). La multiplicación por 6 en números distintos de cero mod 7 tiene descomposición cíclica (1,6) (2,5) (3,4), cuyo signo es −1, que es (6 | 7).
Prueba
En general, para cualquier grupo finito G de orden n , es sencillo para determinar la firma de la permutación π g hecha por multiplicación a la izquierda por el elemento g de G . La permutación π g será par, a menos que haya un número impar de órbitas de tamaño par. Asumiendo n par, por lo tanto, la condición para que π g sea una permutación impar, cuando g tiene el orden k , es que n / k debe ser impar, o que el subgrupo < g > generado por g debe tener un índice impar .
Aplicaremos esto al grupo de números distintos de cero mod p , que es un grupo cíclico de orden p - 1. La j- ésima potencia de una raíz primitiva módulo p tendrá como índice el máximo común divisor
- yo = ( j , p - 1).
La condición para que un número distinto de cero mod p sea un no residuo cuadrático es que sea una potencia impar de una raíz primitiva. Por lo tanto, el lema se reduce a decir que i es impar cuando j es impar, lo cual es cierto a fortiori , y j es impar cuando i es impar, lo cual es cierto porque p - 1 es par ( p es impar).
Otra prueba
El lema de Zolotarev se puede deducir fácilmente del lema de Gauss y viceversa . El ejemplo
- ,
es decir, el símbolo de Legendre ( a / p ) con a = 3 yp = 11, ilustrará cómo va la demostración. Comience con el conjunto {1, 2,. . . , p - 1} organizado como una matriz de dos filas de modo que la suma de los dos elementos en cualquier columna sea cero mod p , digamos:
1 | 2 | 3 | 4 | 5 |
10 | 9 | 8 | 7 | 6 |
Aplicar la permutación :
3 | 6 | 9 | 1 | 4 |
8 | 5 | 2 | 10 | 7 |
Las columnas todavía tienen la propiedad de que la suma de dos elementos en una columna es cero mod p . Ahora aplique una permutación V que intercambie cualquier par en el que el miembro superior era originalmente un miembro inferior:
3 | 5 | 2 | 1 | 4 |
8 | 6 | 9 | 10 | 7 |
Finalmente, aplique una permutación W que recupere la matriz original:
1 | 2 | 3 | 4 | 5 |
10 | 9 | 8 | 7 | 6 |
Tenemos W −1 = VU . El lema de Zolotarev dice ( a / p ) = 1 si y solo si la permutación U es par. El lema de Gauss dice ( a / p ) = 1 si V es par. Pero W es par, por lo que los dos lemas son equivalentes para el dado (pero arbitrario) una y p .
Símbolo de jacobi
Esta interpretación del símbolo de Legendre como el signo de una permutación puede extenderse al símbolo de Jacobi
donde una y n son enteros impares primos con n > 0: una es mod invertible n , por lo que la multiplicación por un sobre Z / n Z es una permutación y una generalización del lema de Zolotarev es que el símbolo de Jacobi anterior es el signo de esta permutación .
Por ejemplo, la multiplicación por 2 en Z / 21 Z tiene un ciclo de descomposición (0) (1,2,4,8,16,11) (3,6,12) (5,10,20,19,17,13) (7,14) (9,18,15), por lo que el signo de esta permutación es (1) (- 1) (1) (- 1) (- 1) (1) = −1 y el símbolo de Jacobi (2 | 21) es −1. (Tenga en cuenta que la multiplicación por 2 en las unidades mod 21 es un producto de dos ciclos de 6, por lo que su signo es 1. Por lo tanto, es importante usar todos los números enteros mod n y no solo las unidades mod n para definir la permutación correcta).
Cuando n = p es un número primo impar y a no es divisible por p , la multiplicación por a fija 0 mod p , por lo que el signo de la multiplicación por a en todos los números mod p y en las unidades mod p tienen el mismo signo. Pero para el compuesto n ese no es el caso, como vemos en el ejemplo anterior.
Historia
Este lema fue introducido por Yegor Ivanovich Zolotarev en una prueba de 1872 de reciprocidad cuadrática .
Referencias
- Zolotareff G. (1872). "Nouvelle démonstration de la loi de réciprocité de Legendre" (PDF) . Nouvelles Annales de Mathématiques . 2e série. 11 : 354–362.
enlaces externos
- Artículo de PlanetMath sobre el lema de Zolotarev; incluye su prueba de reciprocidad cuadrática