5.5: Símbolo Legendre
- Page ID
- 114913
En esta sección, definimos el símbolo Legendre que es una notación asociada a residuos cuadráticos y probamos teoremas relacionados.
Definición: Símbolo Legendre
Dejar\(p\neq 2\) ser un primo y\(a\) ser un entero tal que\(p\nmid a\). El símbolo de Legendre\(\left(\frac{a}{p}\right)\) está definido por
\[\left(\frac{a}{p}\right)=\left\{\begin{array}{lcr} \ 1 &\mbox{if a is a quadratic residue of p} \\ \ -1 &\mbox{if a is a quadratic nonresidue of p}. \\ \end{array}\right .\]
Observe que usando el ejemplo anterior, vemos que
\[\begin{aligned} && \left(\frac{1}{7}\right)=\left(\frac{2}{7}\right)=\left(\frac{4}{7}\right)=1\\ && \left(\frac{3}{7}\right)=\left(\frac{5}{7}\right)=\left(\frac{6}{7}\right)=-1\end{aligned}\]
En el siguiente teorema, presentamos una manera de determinar si un entero es un residuo cuadrático de un primo.
Criterio de Euler
Dejar\(p\neq 2\) ser un primo y dejar\(a\) ser un entero positivo tal que\(p\nmid a\). Entonces
\[\left(\frac{a}{p}\right)\equiv a^{\phi(p)/2}(mod \ p).\]
Asumir eso\(\left(\frac{a}{p}\right)=1\). Entonces la congruencia\(x^2\equiv a(mod \ p)\) tiene una solución digamos\(x=x'\). Según el teorema de Fermat, vemos que
\[a^{\phi(p)/2}=((x')^2)^{\phi(p)/2}\equiv 1(mod\ p).\]
Ahora si\(\left(\frac{a}{p}\right)=-1\), entonces no\(x^2\equiv a(mod \ p)\) es solucionable. Así por el Teorema 26, tenemos que para cada entero k con\((k,p)=1\) hay un entero\(l\) tal que\(kl\equiv a(mod \ p)\). Observe que\(i\neq j\) ya no\(x^2\equiv a(mod \ p)\) tiene soluciones. Así podemos acoplar los enteros\(1,2,...,p-1\) en\((p-1)/2\) pares, cada uno tiene producto\(a\). Multiplicando estos pares juntos, nos enteramos de que
\[(p-1)!\equiv a^{\phi(p)/2}(mod \ p).\]
Usando el teorema de Wilson, obtenemos\[\left(\frac{a}{p}\right)=-1\equiv a^{(p-1)/2}(mod \ p).\]
Dejar\(p=13\) y\(a=3\). Entonces\(\left(\frac{3}{13}\right)=-1\equiv 3^{6}(mod \ 13).\)
Ahora demostramos algunas propiedades del símbolo de Legendre.
\(p\neq 2\)Déjese ser un prime. Dejar\(a\) y\(b\) ser enteros tales que\(p\nmid a\),\(p\nmid b\) y\(p\mid (a-b)\) luego\[\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right).\]
Desde\(p\mid (a-b)\) entonces\(x^2\equiv a(mod \ p)\) tiene una solución si y sólo si\(x^2\equiv b(mod \ p)\) tiene una solución. De ahí\[\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)\]
\(p\neq 2\)Déjese ser un prime. Dejar\(a\) y\(b\) ser enteros tales que\(p\nmid a\),\(p\nmid b\) entonces\[\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)=\left(\frac{ab}{p}\right)\]
Por criterio de Euler, tenemos\[\left(\frac{a}{p}\right)\equiv a^{\phi(p)/2}(mod \ p)\] y\[\left(\frac{b}{p}\right)\equiv b^{\phi(p)/2}(mod \ p).\] Así obtenemos Ahora\[\left(\frac{a}{p}\right)\left(\frac{b}{p}\right) \equiv (ab)^{\phi(p)/2}\equiv \left(\frac{ab}{p}\right)(mod \ p).\] mostramos cuándo es\(-1\) un residuo cuadrático de un primo\(p\).
Si\(p\neq 2\) es un, entonces\[\left(\frac{-1}{p}\right)=\left\{\begin{array}{lcr} \ 1 &{\mbox{if}\ p\equiv 1(mod \ 4)} \\ \ -1 &{\mbox{if}\ p\equiv -1(mod \ 4)}. \\ \end{array}\right .\]
Por criterio de Euler, sabemos que\[\left(\frac{a}{p}\right)=(-1)^{\phi(p)/2}(mod \ p)\] si\(4\mid (p-1)\), entonces\(p=4m+1\) para algún entero\(m\) y así obtenemos\[(-1)^{\phi(p)/2}=(-1)^{2m}=1.\] y si\(4\mid (p-3)\), entonces\(p=4m+3\) para algún entero\(m\) y también obtenemos\[(-1)^{\phi(p)/2}=(-1)^{2m+1}=-1.\]
Ahora determinamos cuándo\(2\) es un residuo cuadrático de un primo\(p\).
Por cada primo impar\(p\) que tenemos
\[\left(\frac{2}{p}\right)=\left\{\begin{array}{lcr} \ 1 &{\mbox{if}\ p\equiv \pm1(mod \ 8)} \\ \ -1 &{\mbox{if}\ p\equiv \pm 3(mod \ 8)}. \\ \end{array}\right .\]
Considera las siguientes\((p-1)/2\) congruencias
\[\begin{aligned} p-1&\equiv& 1(-1)^1 \ \ \ (mod \ p)\\ 2&\equiv& 2(-1)^2 \ \ \ (mod \ p)\\ p-3&\equiv& 3(-1)^3 \ \ \ (mod \ p)\\ 4&\equiv& 4(-1)^4 \ \ \ (mod \ p)\\ &.& \\ &.& \\ &.& \\ r&\equiv& \frac{p-1}{2}(-1)^{(p-1)/2} \ \ \ (mod \ p),\\\end{aligned}\]
donde\(r\) está\(p-(p-1)/2\) o\((p-1)/2\). Multiplicando todas estas ecuaciones obtenemos,
\[2.4.6...(p-1)\equiv \left(\frac{p-1}{2}\right)!(-1)^{1+2+...+(p-1)/2} \ \ \ (mod \ p).\]
Esto nos da
\[2^{(p-1)/2}\left(\frac{p-1}{2}\right)! \equiv \left(\frac{p-1}{2}\right)!(-1)^{(p^2-1)/8} (mod \ p).\]
Ahora fíjate que\(\left(\frac{p-1}{2}\right)!\not\equiv 0(mod \ p)\) y así conseguimos
\[2^{(p-1)/2}\equiv (-1)^{(p^2-1)/8}(mod \ p).\]
Tenga en cuenta también que por criterio de Euler, obtenemos
\[2^{\phi(p)/2}\equiv \left(\frac{2}{p}\right)(mod \ p),\]
y como cada miembro es 1 ó -1 los dos miembros son iguales.
Ahora presentamos un lema importante que determina si un entero es un residuo cuadrático de un primo o no.
Lema de Gauss
Dejar\(p\neq 2\) ser un primo y\(a\) un número entero relativamente primo a\(p\). Si\(k\) cuenta el número de residuos menos positivos de los números enteros\(a, 2a,...,((p-1)/2)a\) que son mayores que\(p/2\), entonces
\[\left(\frac{a}{p}\right)=(-1)^k.\]
Dejar\(m_1,m_2,...,m_s\) ser esos enteros mayores que\(p/2\) en el conjunto de los residuos menos positivos de los enteros\(a, 2a,...,((p-1)/2)a\) y dejar que\(n_1,n_2,...,n_t\) sean aquellos menores que\(p/2\). Ahora demostramos que
\[p-m_1,p-m_2,...,p-m_k,p-n_1,p-n_2,...,p-n_t\]
son precisamente los enteros\[1,2,...,(p-1)/2,\] en el mismo orden.
Entonces demostraremos que no hay dos enteros de estos son módulo congruente\(p\), porque hay exactamente\((p-1)/2\) números en el conjunto, y todos son enteros positivos menores o iguales a\((p-1)/2\). Observe que\(m_i\not\equiv m_j (\mod \ p)\) para todos\(i\neq j\) y\(n_i\not\equiv n_j (\mod \ p)\) para todos\(i\neq j\). Si alguna de estas congruencias falla, entonces tendremos eso\(r\equiv s(mod \ p)\) asumiendo eso\(ra\equiv sa(mod \ p)\). También cualquiera de los enteros\(p-m_i\) puede ser congruente con cualquiera\(n_i\) de los s. porque si tal congruencia se mantiene, entonces tenemos\(ra\equiv p-sa(mod \ p)\), así que eso\(ra\equiv -sa(mod \ p)\). Porque\(p\nmid a\), esto implica eso\(r\equiv -s(mod \ p)\), lo cual es imposible. Concluimos que
\[\prod_{i=1}^k(p-m_i)\prod_{i=1}^tn_i\equiv \left(\frac{p-1}{2}\right)!(mod \ p),\]
lo que implica
\[(-1)^sm_1m_2...(p-m_k)n_1n_2...n_t\equiv \left(\frac{p-1}{2}\right)!(mod \ p),\]
Simplificando, obtenemos
\[m_1m_2...(p-m_k)n_1n_2...n_t\equiv a.2a...((p-1)/2)= a^{(p-1)/2}((p-1)/2)!( mod \ p).\]
Como resultado, tenemos que
\[a^{(p-1)/2}((p-1)/2)!\equiv ((p-1)/2)!(mod \ p)\]
Tenga en cuenta que desde\((p,((p-1)/2)!)=1\), obtenemos
\[(-1)^ka^{(p-1)/2}\equiv 1(mod \ p).\]
Así conseguimos
\[a^{(p-1)/2}\equiv(-1)^k(mod \ p).\]
Utilizando el criterio de Euler, el resultado sigue.
Para encontrar\(\left(\frac{5}{13}\right)\) usando el lema de Gauss, calculamos
\[\sum_{i=1}^6[5i/13]=[5/13]+[10/13]+[15/13]+[20/13]+[25/13]+[30/13]=5\]Así conseguimos\(\left(\frac{5}{13}\right)=(-1)^5=-1\).
Ejercicios
- Encuentra todos los residuos cuadráticos de 3
- Encuentra todos los residuos cuadráticos de 19.
- Encuentra el valor del símbolo Legendre\(\left(\frac{j}{7}\right)\) para\(j=1,2,3,4,5,6\).
- Evaluar el símbolo Legendre\(\left(\frac{7}{11}\right)\) utilizando el criterio de Euler.
- Dejar\(a\) y\(b\) ser enteros no divisibles por\(p\). Mostrar que ya sea uno o los tres de los números enteros\(a,b\) y\(ab\) son residuos cuadráticos de\(p\).
- Dejar\(p\) ser un primo y\(a\) ser un residuo cuadrático de\(p\). Mostrar que si\(p\equiv 1(mod \ 4)\), entonces también\(-a\) es un residuo cuadrático de\(p\), mientras que si\(p\equiv 3(mod \ 4)\), entonces\(-a\) es un no residuo cuadrático de\(p\).
- Mostrar que si\(p\) es un primo impar y a es un entero no divisible para\(p\) entonces\(\left(\frac{a^2}{p}\right)=1\).