Cómo calcular los símbolos de leyenda (105/1009)

Si puede determinar fácilmente si 105 es un residuo cuadrático mod 1009, entonces la respuesta será 1 si lo es, o -1 si no lo es. Probar los 1009 valores y cuadrarlos te dirá cuál es.

La definición de origen de Legendre es

[matemática] \ displaystyle \ left (\ frac {105} {1009} \ right) = 105 ^ {(1009 – 1) / 2} \ pmod {1009} [/ math]

lo que da un segundo método que es mucho menos trabajo, computacionalmente hablando (podemos exponer mediante escuadra repetida).

Otra opción, porque el símbolo de Legendre es una función multiplicativa, es

[matemáticas] \ displaystyle \ left (\ frac {105} {1009} \ right) = \ left (\ frac {3} {1009} \ right) \ left (\ frac {5} {1009} \ right) \ left (\ frac {7} {1009} \ right) [/ math]

Si los dos números en el símbolo de Legendre son primos, entonces podemos usar la ley de reciprocidad cuadrática. Si bien 105 no es primo, 1009 sí lo es, por lo que podemos calcular tres casos fáciles utilizando la reciprocidad cuadrática:

[matemáticas] \ displaystyle \ left (\ frac {3} {1009} \ right) \ left (\ frac {1009} {3} \ right) = (-1) ^ {(1009-1) (3-1) / 4} = (-1) ^ {(1008) (2) / 4} = (-1) ^ {504} = 1 [/ matemáticas]

[matemáticas] \ displaystyle \ left (\ frac {5} {1009} \ right) \ left (\ frac {1009} {5} \ right) = (-1) ^ {(1009-1) (5-1) / 4} = (-1) ^ {1008} = 1 [/ matemáticas]

[matemáticas] \ displaystyle \ left (\ frac {7} {1009} \ right) \ left (\ frac {1009} {7} \ right) = (-1) ^ {(1009-1) (7-1) / 4} = (-1) ^ {(1008) (6) / 4} = (-1) ^ {(504) (3)} = 1 [/ matemáticas]

Así, en los tres casos, los símbolos tienen el mismo signo. Ahora, [matemática] 1009 \ equiv 1 \ pmod {3} [/ matemática], entonces es un residuo cuadrátrico mod 3. [matemática] 1009 \ equiv 4 \ equiv 2 ^ 2 \ pmod {5} [/ matemática], también un residuo cuadrático Y finalmente [matemáticas] 1009 \ equiv 1 \ pmod {7} [/ matemáticas].

Por lo tanto,

[matemáticas] \ displaystyle \ left (\ frac {105} {1009} \ right) = \ left (\ frac {3} {1009} \ right) \ left (\ frac {5} {1009} \ right) \ left (\ frac {7} {1009} \ right) = \ left (\ frac {1009} {3} \ right) \ left (\ frac {1009} {5} \ right) \ left (\ frac {1009} { 7} \ right) = 1 \ times 1 \ times 1 = 1 [/ math]