Sé que $p_i$ es un primo de impar, $(\frac{a}{p_i}\equiv a^{\frac{p_i-1}{2}} \pmod p$ ).
Pero no sé cómo resolver este problema...
Respuesta
¿Demasiados anuncios?
En primer lugar, hay que tener en cuenta que para $(a,n)=1$ , $a^{n-1}\equiv 1 \pmod{n}$ Así que $n$ debe ser un producto de primos Impares distintos, o tendríamos $p\mid \phi(n)$ , por lo que habría $a$ con $(a,n)=1$ y $a$ tiene orden $p$ en el grupo multiplicativo. Pero entonces tendríamos $p\nmid n-1$ , por lo que no podemos tener $a^{n-1}\equiv 1\pmod{n}$ .
Entonces, por el teorema del resto chino, tenemos que $$\newcommand{\ZZ}{\mathbb{Z}}\ZZ/n\ZZ\cong \prod_i \ZZ/p_i\ZZ$$ para $p_i$ primos Impares distintos. Entonces, mirando por coordenadas, vemos que para cada primo $p_i$ , $a^{(n-1)/2}\equiv \left(\frac{a}{n}\right)\pmod{p_i}$ . Supongamos por contradicción que $n$ no es a su vez primo, por lo que $n/p_i\ne 1$ . Entonces, multiplicando cada lado de nuestra ecuación por $\left(\frac{a}{p_i}\right)$ tenemos $$a^{(p_i(n/p_i)+p_i)/2-1}=a^{p_i(n/p_i+1)/2 - 1}=a^{-1}(a^{p_i})^{(n/p_i+1)/2}=a^{(n/p_i-1)/2}=\left(\frac{a}{n/p_i}\right)\pmod{p_i}.$$
Ahora, en particular, esto es cierto para $i=1$ . Es decir, tenemos que $$a^{(n/p_1-1)/2}=\left(\frac{a}{n/p_1}\right)\pmod{p_1}.$$ Sin embargo, aplicando el teorema chino del resto, podemos elegir $a$ para ser 1 mod $p_i$ para $i\ne 2$ y $a$ para ser un mod no cuadrado $p_2$ . Entonces esta ecuación se convierte en $$1=-1 \pmod{p_1}.$$
Contradicción. Por lo tanto, $n$ debe ser primo.
