Ayuda en esta prueba de los símbolos de Legendre

Question

Necesito ayuda en la segunda parte de este teorema:

No he entendido la segunda parte de este teorema:

1. ¿Por qué podemos elegir tal $j$ y $j'$ ?

2. ¿Qué quiere decir el autor con "la contribución combinada $j$ y $j'$ a $(p-1)!$ es $jj'\equiv a (\mod p)$ "?

3. por qué hay $(p-1)/2$ ¿dichas parejas?

Realmente necesito ayuda y estaría muy agradecida si alguien pudiera ayudarme.

¡Muchas gracias!

Answer 1

Damos lo que es esencialmente la misma prueba, pero la redacción será diferente. Entiendo que no has tenido problemas con la parte de la prueba que dice que si el símbolo de Legendre $(a/p)$ es $1$ lo que significa que $a$ es un QR de $p$ entonces $a^{(p-1)/2}\equiv 1 \pmod{p}$ .

Queremos demostrar que si $(a/p)=-1$ , lo que significa que $a$ es un NR de $p$ entonces $a^{(p-1)/2}\equiv -1\pmod{p}$ .

Mira los números de $1$ a $p-1$ . Si $x$ y $y$ están en este intervalo, llame a $x$ y $y$ socios si $xy\equiv a\pmod{p}$ . Primero demostramos que cada $y$ tiene un socio. Desde $y$ y $p$ son relativamente primos, por La identidad de Bézout existen enteros $s$ y $t$ tal que $sy+tp=1$ . De ello se desprende que $(as)y+atp=a$ y por lo tanto $$(as)y\equiv a\pmod{p}.$$ Dejemos que $x$ sea el resto cuando $as$ se divide por $p$ . Entonces $1\le x\le p-1$ y $xy\equiv a \pmod{p}$ . Este $x$ es el socio de $y$ . El $x$ es único, ya que si $xy\equiv x'y\equiv a \pmod{p}$ entonces, por cancelación $x\equiv x'\pmod{p}$ .

Tenga en cuenta que $y$ nunca es su propia pareja, porque si lo fuera tendríamos $y^2\equiv a\pmod{p}$ , contradiciendo el hecho de que $a$ es un NR de $p$ .

Así, los números de $1$ a $p-1$ se dividen en parejas. Evidentemente, hay $(p-1)/2$ parejas, ya que hay $p-1$ personas.

El producto de los dos números de cualquier pareja es congruente con $a$ modulo $p$ . Esto es por la definición de pareja.

Hay $(p-1)/2$ parejas, cada una de las cuales tiene un producto congruente con $a$ . Así que el producto de todo los números del intervalo $1$ a $p-1$ es congruente con $a^{(p-1)/2}$ modulo $p$ . Pero por el Teorema de Wilson el producto de todos los números de $1$ a $p-1$ es congruente con $-1$ modulo $p$ .

De ello se desprende que $a^{(p-1)/2}\equiv -1\pmod{p}$ .