ALGUNAS APLICACIONES DE LOS RESIDUOS CUADRATICOS
Recordamos que un número a es residuo cuadrático
[1] de un primo q, si existe un valor n para el que se cumple
(1):
\(n^2 \equiv a\; (mod \; q) \)
Según el criterio de Euler, tenemos (2) :
\(a^{(q-1)/2}\equiv \pm 1\; (mod \; q) \)
Cuando el resultado es +1, decimos que a es residuo cuadrático
módulo p, y cuando el resultado es -1, decimos que a
es No residuo cuadrático módulo p.
TEOREMA
Para todo primo \( p = 4n+1 \), si m es un residuo cuadrático
módulo p, entonces -m también es un residuo cuadrático
módulo p. Para todo primo \( p = 4n+3 \), si m es un residuo
cuadrático módulo p, entonces -m no es un residuo
cuadrático módulo p.
Demostración
Considerando el símbolo de Legrende se cumple (3):
\(\left(
\begin{array}{c}
m \\
p \\
\end{array}
\right)\left(
\begin{array}{c}
-m \\
p \\
\end{array}
\right)= (-1)^{(p-1)/2}\)
Según el pequeño teorema de Fermat y el criterio
de Euler, siendo p un primo impar, tenemos para todo m (4) :
\(\left(
\begin{array}{c}
m \\
p \\
\end{array}
\right)\equiv m^{(p-1)/2}\; (mod \; p)= \left\{
\begin{array}{c}
+1\; Si \; mRp \\
-1\; Si \; m\bar{R}p \\
\end{array}
\right. \)
Por lo que si \( p = 4n+1 \) (5):
\( (-m)^{(p-1)/2} = (-m)^{2n}= \left[(-m)^2\right]^n = (m)^{2n}=(m)^{(p-1)/2}\)
y si \( p = 4n+3 \) (6):
\(\begin{array}{l}
(-m)^{(p-1)/2} = (-m)^{2n+1}= \left[(-m)^2\right]^n(-m) =
\\
\\
= -m(m)^{2n}=-m^{2n+1}=m^{(p-1)/2}
\end{array}
\)
y queda demostrado lo que nos proponíamos.
Las propiedades de los residuos cuadráticos nos permiten
caracterizar algunos primos para los cuales es posible deducir
a priori algún factor de \( (a^p \pm b^p) \).
Sean \(p \; y \; q = 2p+1 \) primos ; existirán valores
a y b que serán simultánea o alternativamente residuos
cuadráticos respecto al primo q; es decir , se tendrá
alguna de las posibilidades (a SR, b SR), (a SR, b NR), (a NR,
b SR), (a NR, b NR) que, para el tema que nos ocupa, pueden reducirse
a las dos primeras (7) :
\(\begin{array}{l}
a^{(q-1)/2}\equiv +1\; (mod \; q)\,;\,b^{(q-1)/2}\equiv +1\; (mod \; q)\Leftrightarrow\\ \\ a^p\equiv +1\; (mod \; q)\,;\,b^p\equiv +1\; (mod \; q) \\
\\
a^{(q-1)/2}\equiv +1\; (mod \; q)\,;\,b^{(q-1)/2}\equiv -1\; (mod \; q)\Leftrightarrow \\ \\a^p\equiv +1\; (mod \; q)\,;\,b^p\equiv -1\; (mod \; q)
\end{array} \)
De las que es fácil deducir criterios de divisibilidad
.
Para 2 tenemos (8):
\(\begin{array}{l}
2^{(q-1)/2}\equiv +1\; (mod \; q)\Leftrightarrow q\equiv \pm
1\; (mod \; 8) \\
2^{(q-1)/2}\equiv -1\; (mod \; q)\Leftrightarrow q\equiv \pm
3\; (mod \; 8)
\end{array} \)
Con lo que los primos p tales que \( q = 2p+1 \) es un factor
primo de \( 2^p+1 \; ó \; 2^p - 1 \), son (9) :
\( \begin{array}{l}
p\equiv 3\; (mod \; 4)\Leftrightarrow 2p\equiv 6\; (mod \; 8)\Rightarrow
\\ q = 2p+1 \equiv 7\; (mod \; 8)\Rightarrow q \;factor \; de
\; 2^p - 1
\\ \\
p\equiv 1\; (mod \; 4)\Leftrightarrow 2p\equiv 2\; (mod \; 8)\Rightarrow
\\ q = 2p+1 \equiv 3\; (mod \; 8)\Rightarrow q \;factor \; de
\; 2^p + 1
\end{array}\)
Para 3 tenemos (10) :
\(\begin{array}{l}
3^{(q-1)/2}\equiv +1\; (mod \; q)\Leftrightarrow q\equiv \pm
1\; (mod \; 12) \\
3^{(q-1)/2}\equiv -1\; (mod \; q)\Leftrightarrow q\equiv \pm
5\; (mod \; 12)
\end{array} \)
Con lo que los primos p tales que \( q = 2p+1 \) es un factor
primo de \( 3^p+1 \), son
(11) :
\( \begin{array}{l}
p\equiv 5\; (mod \; 6)\Leftrightarrow 2p\equiv 10\; (mod \;
12)\Rightarrow \\ q = 2p+1 \equiv 11\; (mod \; 12)\Rightarrow
q \;factor \; de \; 3^p - 1 \end{array}\)
No existe ningún primo q para el que 3 sea un no residuo
cuadrático y tal que (q-1)/2 sea primo.
Para 4 tenemos : 4 = 2², con lo que dicho valor es residuo
cuadrático para todo primo > 3 y, por lo tanto, todos
los números p = (q-1)/2 que sean primos darán
un valor múltiplo de q para (4p-1)/3.
Para 5 tenemos (12) :
\(\begin{array}{l}
5^{(q-1)/2}\equiv +1\; (mod \; q)\Leftrightarrow q\equiv \pm
1\; (mod \; 12) \\
5^{(q-1)/2}\equiv -1\; (mod \; q)\Leftrightarrow q\equiv \pm
3\; (mod \; 12)
\end{array} \)
Con lo que los primos p tales que \( q = 2p+1 \) es un factor
primo de \( 5^p+1 \; ó \; 5^p - 1 \), son (13) :
\(\begin{array}{l}
p\equiv 4\; (mod \; 5)\Leftrightarrow 2p\equiv 8\; (mod \; 10)\Rightarrow \\ q = 2p+1 \equiv 9\; (mod \; 10)\Rightarrow q \;factor \; de \; 5^p - 1 \\
\\
p\equiv 3\; (mod \; 5)\Leftrightarrow 2p\equiv 6\; (mod \; 10)\Rightarrow \\ q = 2p+1 \equiv 7\; (mod \; 10)\Rightarrow q \;factor \; de \; 5^p + 1 \\
\\
p\equiv 2\; (mod \; 5)\Leftrightarrow 2p\equiv 4\; (mod \; 10)\Rightarrow \\ q = 2p+1 \equiv 5\; (mod \; 10)\Rightarrow q \; no \; es \; primo \\
\\
p\equiv 1\; (mod \; 5)\Leftrightarrow 2p\equiv 2\; (mod \; 10)\Rightarrow \\ q = 2p+1 \equiv 3\; (mod \; 10)\Rightarrow q \;factor \; de \; 5^p + 1
\end{array} \)
Para 6 tenemos que este número será residuo cuadrático
cuando lo sean o no lo sean, simultáneamente, 2 y 3.
Y tenemos :
\(\begin{array}{l}
2Rp \Leftrightarrow p\equiv \pm 1\; (mod \; 8) \; ;\; 2\bar{R}p
\Leftrightarrow p\equiv \pm 3\; (mod \; 8) \\ \\
3Rp \Leftrightarrow p\equiv \pm 1\; (mod \; 12) \; ;\; 2\bar{R}p
\Leftrightarrow p\equiv \pm 5\; (mod \; 12)
\end{array} \)
Tenemos cuatro casos distintos en los que 2 y 3 son simultáneamente
residuos cuadráticos (15):
\(\begin{array}{l} \left. \begin{array}{l} \left. \begin{array}{l}
p=8+1 \Rightarrow 3p=24x+3 \\ \\ p=12x+1 \Rightarrow 2p=24x+2
\end{array} \right\}p=24x + 1 \\\\\\ \left. \begin{array}{l}
p=8x-1 \Rightarrow 3p=24x-3 \\ \\ p=12x-1 \Rightarrow 2p=24x-2
\end{array} \right\}p=24x - 1 \\ \end{array} \right\} p\equiv
\pm 1\; (mod \; 24) \\ \\\\\\ \\ \left. \begin{array}{l}
\left. \begin{array}{l} p=8x+1 \Rightarrow 3p=24x+3 \\ \\ p=12x-1
\Rightarrow 2p=24x-2 \end{array} \right\}p=24x + 5 \\\\\\ \left.
\begin{array}{l} p=8x-1 \Rightarrow 3p=24x-3 \\ \\ p=12x+1 \Rightarrow
2p=24x+2 \end{array} \right\}p=24x -5 \\ \end{array} \right\}
p\equiv \pm 5\; (mod \; 24) \end{array} \)
Repitiendo el proceso cuando 2 y 3 son simultáneamente
No residuos cuadráticos, llegamos al resultado (16):
\(\begin{array}{l}
6^{(q-1)/2}\equiv + 1\; (mod \; q)\Leftrightarrow q \equiv \pm
1\; (mod \; 24)\; ; \;\pm 5\; (mod \; 24) \\
\\
6^{(q-1)/2}\equiv -1\; (mod \; q)\Leftrightarrow q \equiv \pm
7\; (mod \; 24)\; ; \;\pm 11\; (mod \; 24)
\end{array}
\)
Con lo que los primos p tales que \( q = 2p+1 \) es un factor
primo de \( 6^p+1 \; ó \; 6^p - 1 \), son (17) :
\( \begin{array}{l}
p\equiv 11\; (mod \; 12)\Leftrightarrow 2p\equiv 22\; (mod \;
24)\Rightarrow \\ q = 2p+1 \equiv 23\; (mod \; 24)\Rightarrow
q \;factor \; de \; 6^p - 1
\\ \\
p\equiv 5\; (mod \; 12)\Leftrightarrow 2p\equiv 10\; (mod \;
24)\Rightarrow \\ q = 2p+1 \equiv 11\; (mod \; 24)\Rightarrow
q \;factor \; de \; 6^p + 1
\end{array}\)
Para 7 tenemos (18) :
\(\begin{array}{l}
7^{(q-1)/2}\equiv + 1\; (mod \; q)\Leftrightarrow q \equiv \pm
1\; (mod \; 28)\; ; \;\pm 3\; (mod \; 28)\; ; \;\pm 9\; (mod
\; 28) \\
\\
7^{(q-1)/2}\equiv -1\; (mod \; q)\Leftrightarrow q \equiv \pm
5\; (mod \; 28)\; ; \;\pm 11\; (mod \; 28)\; ; \;\pm 13\; (mod
\; 28)
\end{array} \)
Con lo que los primos p tales que \( q = 2p+1 \) es un factor
primo de \( 7^p+1 \; ó \; 7^p - 1 \), son (19):
\( \begin{array}{l}
p=14n+1\Leftrightarrow q\equiv 3\; (mod \; 28)\Rightarrow q
\;factor \; de \; 7^p - 1 \\
\\
p=14n+5\Leftrightarrow q\equiv 11\; (mod \; 28)\Rightarrow q
\;factor \; de \; 7^p + 1 \\
\\
p=14n+9\Leftrightarrow q\equiv -9\; (mod \; 28)\Rightarrow q
\;factor \; de \; 7^p - 1 \\
\\
p=14n+11\Leftrightarrow q\equiv -5\; (mod \; 28)\Rightarrow
q \;factor \; de \; 7^p + 1 \\
\\
p=14n+13\Leftrightarrow q\equiv -1\; (mod \; 28)\Rightarrow
q \;factor \; de \; 7^p - 1
\end{array}\)
Para 8 tenemos la misma situación que para 2, es decir,
los primos p tales que \( q = 2p+1 \) es un factor primo de\( 8^p+1 \; ó \; 8^p - 1 \) , son los que
cumplen (9).
Para 9 tenemos : 9 = 3², con lo que dicho valor es residuo
cuadrático para todo primo > 7 y, por lo tanto, todos
los números p = (q-1)/2 que sean primos darán
un valor múltiplo de q para \( (9^p-1)/3 \).
Para 10 tenemos una situación análoga a 6, y operando
de modos similar resulta (20) :
\( \begin{array}{l}
10^{(q-1)/2}\equiv + 1\; (mod \; q)\Leftrightarrow \\ q \equiv \pm
1\; (mod \; 40)\; ; \;\pm 3\; (mod \; 40)\; ; \;\pm 9\; (mod \; 40)\; ; \;\pm 13\; (mod \; 40) \\
\\
10^{(q-1)/2}\equiv - 1\; (mod \; q)\Leftrightarrow \\ q \equiv \pm
7\; (mod \; 40)\; ; \;\pm 11\; (mod \; 40)\; ; \;\pm 17\; (mod \; 40)\; ; \;\pm 19\; (mod \; 40)
\end{array} \)
Con lo que los primos p tales que \( q = 2p+1 \) es un factor
primo de \( 10^p+1 \; ó \; 10^p - 1 \), son (21) :
\(\begin{array}{l}
p=20n+1\Leftrightarrow q\equiv 3\; (mod \; 40)\Rightarrow q
\;factor \; de \; 10^p - 1 \\
\\
p=20n+3\Leftrightarrow q\equiv 7\; (mod \; 40)\Rightarrow q
\;factor \; de \; 10^p + 1 \\
\\
p=20n+9\Leftrightarrow q\equiv 19\; (mod \; 40)\Rightarrow q
\;factor \; de \; 10^p + 1 \\
\\
p=20n+13\Leftrightarrow q\equiv 27\; (mod \; 40)\Rightarrow
q \;factor \; de \; 10^p - 1 \\
\\
p=20n+19\Leftrightarrow q\equiv 39\; (mod \; 40)\Rightarrow
q \;factor \; de \; 10^p - 1
\end{array} \)
Para otros números tendríamos desarrollos análogos.
EJEMPLOS
Si \( p \; y \; q = 4p+1 \)son números primos, entonces
2 y 3 son raices primitivas de q y se cumple (22):
\( 4^p + 1\equiv 0\; (mod \; q) \; ; \;9^p + 1\equiv 0\; (mod
\; q)\)
Demostración
Según el pequeño teorema de Fermat, podemos escribir
(23) :
\( \begin{array}{l}
2^{(q-1)}-1\equiv 0\; (mod \; q)\Leftrightarrow 2^{4p}-1\equiv
0\; (mod \; q)\Leftrightarrow \left(2^{2p}+1\right)\left(2^{2p}-1\right)\equiv
0\; (mod \; q) \\
\\
3^{(q-1)}-1\equiv 0\; (mod \; q)\Leftrightarrow 3^{4p}-1\equiv
0\; (mod \; q)\Leftrightarrow \left(3^{2p}+1\right)\left(3^{2p}-1\right)
\equiv 0\; (mod \; q)\\
\end{array}\)
Sólo uno de los factores de cada una de las expresiones
anteriores es múltiplo de q, pues en otro caso, restando
un factor de otro, resultaría que 2 divide a q lo cual
es imposible por ser q un número primo impar.
Por otro lado, todo primo impar puede escribirse en la forma \(
p = 2n-1 \) y todo primo impar, salvo el 3, puede escribirse en
una de las formas \(( p = 3n+1 \; ó \; p = 3n+2 )\). Según
eso (24) :
\(\begin{array}{l}
q=4p+1 = 4(2n-1)+1 = 8n-3 \\
\\
q=4p+1 = 4(3n+1)+1 = 12n+5 \\
\\
q=4p+1 = 4(3n+2)+1 = 12n+9 = 3(4n+3)
\end{array} \)
De la primera ecuación de (24) se deduce que 2 es un
NO residuo cuadrático módulo q y, por lo tanto,
se cumplirá (25) :
\(2^{(q-1)/2}\equiv - 1\; (mod \; q)\Leftrightarrow 2^{2p}+1\equiv
0\; (mod \; q) \)
De la segunda ecuación de (24) se deduce que 3 es un
NO residuo cuadrático módulo q y se cumplirá
(26) :
\(3^{(q-1)/2}\equiv - 1\; (mod \; q)\Leftrightarrow 3^{2p}+1\equiv
0\; (mod \; q) \)
Es trivial verificar que (27) :
\(2^4\neq 1 \; (mod \; q) \quad y \quad 3^4\neq 1 \; (mod \;
q) \)
para cualquier primo q tal que \( q = 4p+1 \) , por lo que ambos
valores cumplen las condiciones para ser raices primitivas módulo
q.
Finalmente, de (25) y (26) resulta (28) :
\(4^p + 1\equiv 0\; (mod \; q)\quad y \quad 9^p+1\equiv 0\;
(mod \; q) \)
y hemos demostrado lo que nos proponíamos.
Si \(p \; y \;q = 6p+1 \) son números primos, se cumple
(29) :
\(\begin{array}{l}
27^p + 1 \equiv 0\; (mod \; q) \\
\\
8^p + 1 \equiv 0\; (mod \; q)\; si \; p=4n+3 \\
\\
8^p - 1 \equiv 0\; (mod \; q)\; si \; p=4n+1
\end{array} \)
Demostración
Según el pequeño teorema de Fermat, podemos escribir
(30) :
\(\begin{array}{l}
2^{(q-1)}-1\equiv 0\; (mod \; q)\Leftrightarrow 2^{6p}-1\equiv
0\; (mod \; q)\Leftrightarrow \left(2^{3p}+1\right)\left(2^{3p}-1\right)
\\
3^{(q-1)}-1\equiv 0\; (mod \; q)\Leftrightarrow 3^{6p}-1\equiv
0\; (mod \; q)\Leftrightarrow \left(3^{3p}+1\right)\left(3^{3p}-1\right)
\\
\end{array} \)
Sólo uno de los factores de cada una de las expresiones
anteriores es múltiplo de q, pues en otro caso, restando
un factor de otro, resultaría que 2 divide a q lo cual
es imposible por ser q un número primo impar.
Por otro lado, todo primo impar puede escribirse en la forma \( p = 2n+1 \) y todo primo impar puede escribirse en una de las
formas \( (p = 4n+1 \; ó \; p = 4n+3) \). Según
eso (31) :
\(\begin{array}{l}
q=6p+1 = 6(2n+1)+1 = 12n+7 \\
q=6p+1 = 6(4n+1)+1 = 24n+7 = 8(3n)+7\\
q=6p+1 = 6(4n+3)+1 = 24n+19 = 8(3n+2)+3
\end{array}
\)
De la primera ecuación de (31) se deduce que 3 es un
NO residuo cuadrático módulo q y, por lo tanto,
se cumplirá (32) :
\(3^{(q-1)/2}\equiv -1\; (mod \; q)\Rightarrow 3^{3p}+1\equiv
0\; (mod \; q)\Rightarrow 27^p +1\equiv 0\; (mod \; q) \)
De la segunda ecuación de (31) se deduce que 2 es un
residuo cuadrático módulo q y se cumplirá
(33) :
\(2^{(q-1)/2}\equiv 1\; (mod \; q)\Rightarrow 2^{3p}-1\equiv
0\; (mod \; q)\Rightarrow 8^p -1\equiv 0\; (mod \; q) \)
De la tercera ecuación de (31) se deduce que 2 es un
NO residuo cuadrático módulo q y se cumplirá
(34) :
\( 2^{(q-1)/2}\equiv -1\; (mod \; q)\Rightarrow 2^{3p}+1\equiv
0\; (mod \; q)\Rightarrow 8^p +1\equiv 0\; (mod \; q) \)
BIBLIOGRAFIA
1.- Apóstol, T.M. Introducción a la teoría
analítica de números. Ed. Reverté
2.- A. Vera Lopez y R. Esteban Romero. Problemas y ejercicios
de matemática discreta, Ed A.V.L.
3.- Aparicio, E., Teoría de los Números, Servicio
Editorial U.P.V.
4.- Cilleruelo, J. ; Córdoba, A., La teoría de
los Números, Biblioteca Mondadori.
| |
¿Te han sido de utilidad
estos apuntes sobre los resíduos cuadráticos?.-
¡Recomiénda esta página!
|
|
|
| |
|
|
Otros usuarios de Matemáticas y poesía también
han visto:
|
|
|