Estás en > Matemáticas y Poesía > Matemáticas

MONOGRAFIAS MATEMÁTICAS
TEORÍA DE NÚMEROS

RESÍDUOS CUADRÁTICOS

 

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:


 


tema escrito por: José Antonio Hervás