En teoría de números , el lema de Zolotarev establece que el símbolo de Legendre
Para un entero a módulo un número primo impar p , donde p no divide a 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, tomemos a = 2 y p = 7. Los cuadrados distintos de cero módulo 7 son 1, 2 y 4, por lo que (2|7) = 1 y (6|7) = −1. La multiplicación por 2 de los números distintos de cero módulo 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 de los números distintos de cero módulo 7 tiene la descomposición cíclica (1,6)(2,5)(3,4), cuyo signo es −1, que es (6|7).
En general, para cualquier grupo finito G de orden n , es sencillo determinar la firma de la permutación π g hecha por multiplicación 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. Por lo tanto, suponiendo que n es par, la condición para que π g sea una permutación impar, cuando g tiene orden k , es que n / k debe ser impar, o que el subgrupo < g > generado por g debe tener índice impar .
Aplicaremos esto al grupo de números distintos de cero módulo p , que es un grupo cíclico de orden p − 1. La j -ésima potencia de una raíz primitiva módulo p tendrá índice el máximo común divisor.
La condición para que un número distinto de cero módulo p sea un residuo cuadrático no nulo 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).
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 y p = 11, ilustrará cómo se desarrolla la prueba. 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 módulo p , digamos:
Aplicar la permutación :
Las columnas aún tienen la propiedad de que la suma de dos elementos en una columna es cero módulo p . Ahora aplique una permutación V que intercambie todos los pares en los que el miembro superior era originalmente un miembro inferior:
Finalmente, aplicamos una permutación W que recupera la matriz original:
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 y solo si V es par. Pero W es par, por lo que los dos lemas son equivalentes para los valores dados (pero arbitrarios) a y p .
Esta interpretación del símbolo de Legendre como signo de una permutación puede extenderse al símbolo de Jacobi.
donde a y n son números enteros relativamente primos con n impar > 0: a es invertible módulo n , por lo que la multiplicación por a en 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 descomposición cíclica (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 módulo 21 es un producto de dos 6-ciclos, por lo que su signo es 1. Por lo tanto, es importante utilizar todos los números enteros módulo n y no solo las unidades módulo n para definir la permutación correcta).
Cuando n = p es un 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.
Este lema fue introducido por Yegor Ivanovich Zolotarev en una prueba de reciprocidad cuadrática de 1872 .
