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

MONOGRAFIAS MATEMÁTICAS
TEORÍA DE NÚMEROS

DIVISIBILIDAD DE EXPRESIONES NUMÉRICAS

 

ESTUDIO DE LAS PROPIEDADES DE DIVISIBILIDAD DE CIERTAS EXPRESIONES NUMERICAS

INTRODUCCION

A lo largo de estas notas vamos a reflejar algunos resultados particulares obtenidos en relación con la factorización de expresiones de la forma (1):

    \(A^xB^y + C^uD^v\)
DESARROLLO

Dentro de esta caracterización general entrarían expresiones tales como (2):
    \(a^n \pm b^n \;;\; ab^n + k\)
que están relacionadas entre sí, como vemos a continuación.

Supongamos que existen dos valores x e y, para el exponente m, de (2) tales que (3):
    \( ab^x + k \equiv 0 (mod \; p)\; ; \; ab^y + k \equiv 0 (mod \; p)\)
Restando una expresión de la otra tenemos (4):
    \( ab^x[b^{y-x} - 1] \equiv 0 (mod \; p)\)
En general, \( ab^x\) no será múltiplo de p, por lo que deberá serlo la expresión entre corchetes. Por el teorema de Euler Fermat, sabemos que existen números que cumplen lo anterior.

Aplicando la teoría de índices de raíces primitivas [1], [2], podemos deducir que números de la forma (3) son múltiplos de un primo dado. A partir de (3), podemos poner (5):
    \(ind_g a + ind_g b·x \equiv - ind_gk \quad (mod[p-1])\)
Cuya solución, cuando (indg b , p-1) = 1, viene dada por [2] (6) :
    \( x \equiv -[ind_g b]^{\varphi(p-1)-1}[ind_g k + ind_g a]\; (mod[p-1]) \)
donde \( \varphi(·)\)es la función de Euler.

EJEMPLOS

Ver cuando es múltiplo de 17, 31 ó 47 la expresión (7) \(2\times5^x + 1\) :

Tomando índices [1] para cada valor, resulta (8) :
    \(\begin{array}{l} 14 + 5x \equiv 8 (mod \;16)\Rightarrow 5x \equiv -6 (mod\; 16) \\ \\ 24 + 20x \equiv 15 (mod \;30)\Rightarrow 20x \equiv -9 (mod\; 30) \\ \\ 18 + 5x \equiv 23 (mod \;46)\Rightarrow x \equiv 5 (mod \;46) \end{array}\)
En el segundo caso no tenemos (a,m) = 1 si no (a,m) = d = 10 y, de acuerdo con [2], como (d,b) (10,9) = 1, la congruencia no tiene solución.
En el tercer caso obtenemos la solución directamente y en el primero es mas cómodo obtenerla dando valores a la variable "y" en la expresión :
    \(5x = 16y - 6 \Rightarrow (y = 1) \Rightarrow x = 2\)
En conclusión, la expresión (7) es múltiplo de 17 cuando x = 16y + 2, no es múltiplo de 31 para ningún valor de x, y es múltiplo de 47 cuando x = 46y + 5.
También podemos ver que (7) no puede ser simultáneamente múltiplo de 17 y 47, pues en ese caso debería cumplirse :
    \(16y_1 + 2 = 46y_2 + 5 \Rightarrow 16y_1 - 46y_2 = 3\)
y, de acuerdo con la teoría de resolución de ecuaciones diofánticas lineales [3] la ecuación anterior no tiene solución en números enteros.
Las propiedades de las congruencias nos permiten deducir diversos criterios de divisibilidad :

TEOREMA

Si la expresión \(a·b^n + k\) es múltiplo de un primo p, entonces (10) :
    \(a·b^{n+(p-1)m} + k\equiv 0 \;(mod\; p) \; y \; a(b+m·p)^n + k\equiv 0 \;(mod\; p) \)
para cualquier valor natural de m.

Demostración

Según el teorema de Euler Fermat, se cumple (11) :
    \((b^m)^{p-1}-1 \equiv 0 (mod \; p) \Rightarrow b^{(p-1)m}-1 \equiv 0 (mod \; p) \)
y, a partir de ahí (12) :
    \( ab^n[b^{(p-1)m}-1]= ab^{n+(p-1)m}- ab^n \equiv 0 (mod \; p) \)
pero, teniendo en cuenta (9) resulta (13) :
    \(a·b^{n+(p-1)m} + k\equiv 0 (mod \; p) \)
En particular, si \(a·b + k = p\) tenemos (14) :
    \(a·b^p + k\equiv a^p b \equiv 0 (mod \; p) \)
Para la segunda ecuación de (10) el resultado es trivial (15) :
    \(\left.
    \begin{array}{c}
    ab^n + k \equiv 0 (mod \; p) \\
    m·p \equiv 0 (mod \; p) \\
    \end{array}
    \right\}\; a(b+0)^n \equiv 0 (mod \; p)\Rightarrow a(b+m·p)^n \equiv 0 (mod \; p) \)
Por ejemplo, para el primo 3, tenemos (16) :
    \(\begin{array}{c} a = 2 (mod \;3) \; ; \; b = 1 (mod\; 3) \; ; \; k = 1 (mod \;3) \Rightarrow ab^m + k = 0 (mod \;3) \\ a = 1 (mod \;3) \; ; \; b = 1 (mod\; 3) \; ; \; k = 2 (mod \;3) \Rightarrow ab^m + k = 0 (mod \;3) \\ a = 1 (mod\; 3) \; ; \; b = 2 (mod \;3) \; ;\; k = 1 (mod 3) \Rightarrow ab^{2m+1} + k = 0 (mod \;3) \\ a = 2 (mod\; 3) \; ; \; b = 2 (mod \;3) \; ;\; k = 1 (mod 3) \Rightarrow ab^{2m+1} + k = 0 (mod \;3) \\ a = 1 (mod\; 3) \; ; \; b = 2 (mod \;3) \; ;\; k = 2 (mod 3) \Rightarrow ab^{2m+1} + k = 0 (mod \;3) \\ a = 1 (mod\; 3) \; ; \; b = 1 (mod \;3) \; ;\; k = 2 (mod 3) \Rightarrow ab^{2m+1} + k = 0 (mod \;3) \end{array}\)
TEOREMA

Para todo primo\(p \equiv \pm 3 \; (mod \; 8)\)) se cumple (22) :
    \(\displaystyle 2\left(\frac{p-1}{a}\right)^{\frac{p+1}{2}} + 1 \equiv 0 (mod \; p) \)
Demostración

Para todo primo \(p \equiv \pm 3 \; (mod \; 8)\), 2 es NO residuo cuadrático y se cumple (23) :
    \( \begin{array}{c} 2^{(p-1)/2} + 1 \equiv 0 (mod \; p) \Rightarrow 2^{\frac{p+1}{2}-1}+1 \equiv 0 (mod \; p)\Rightarrow \\ \\ \displaystyle \Rightarrow \frac{1}{2} 2^{\frac{p+1}{2}}+1 \equiv 0 (mod \; p) \Rightarrow 2^{\frac{p+1}{2}}+2 \equiv 0 (mod \; p) \end{array} \)
Además, p+1 siempre es residuo cuadrático módulo p y tendremos (24) :
    \(\begin{array}{c}
    (p+1)^{(p-1)/2} -1 \equiv 0 (mod \; p)\Rightarrow (p+1)^{\frac{p+1}{2}-1}-1 \equiv 0 (mod \; p)\Rightarrow \\
    \\
    \displaystyle \Rightarrow \frac{1}{p+1}(p+1)^{\frac{p+1}{2}}-1 \equiv 0 (mod \; p)\Rightarrow (p+1)^{\frac{p+1}{2}}-1 \equiv 0 (mod \; p)
    \end{array} \)
Por lo tanto, multiplicando la ecuación final de (23) por 2 y sumándole la ecuación final de (22), llegamos al resultado que pretendíamos.

TEOREMA

Para todo primo p ≡ ± 1 (mod 8) se cumple (25) :
    \(\displaystyle 2\left(\frac{p+1}{a}\right)^{\frac{p+1}{2}} - 1 \equiv 0 (mod \; p) \)
Demostración

Para todo primo p ≡ ± 1 (mod 8), 2 es residuo cuadrático y se cumple (26) :
    \( \begin{array}{c} 2^{(p-1)/2} - 1 \equiv 0 (mod \; p) \Rightarrow 2^{\frac{p+1}{2}-1}-1 \equiv 0 (mod \; p)\Rightarrow \\ \\ \displaystyle \Rightarrow \frac{1}{2} 2^{\frac{p+1}{2}}-1 \equiv 0 (mod \; p) \Rightarrow 2^{\frac{p+1}{2}}-2 \equiv 0 (mod \; p) \end{array} \)
Además, p+1 siempre es residuo cuadrático módulo p y tendremos (27) :
    \(\begin{array}{c}
    (p+1)^{(p-1)/2} -1 \equiv 0 (mod \; p)\Rightarrow (p+1)^{\frac{p+1}{2}-1}-1 \equiv 0 (mod \; p)\Rightarrow \\
    \\
    \displaystyle \Rightarrow \frac{1}{p+1}(p+1)^{\frac{p+1}{2}}-1 \equiv 0 (mod \; p)\Rightarrow (p+1)^{\frac{p+1}{2}}-1 \equiv 0 (mod \; p)
    \end{array} \)
Por lo tanto, multiplicando la ecuación final de (27) por 2 y restándole la ecuación final de (26), llegamos al resultado que pretendíamos.

TEOREMA

Si p es un primo que tiene el mismo módulo respecto a 4 y a 8, entonces se cumple (28) :
    \(\displaystyle 2\left(\frac{p-1}{2}\right)^{\frac{p+1}{2}} + 1 \equiv 0 (mod \; p) \)
Demostración

Sólo podemos tener (29) :
    \( \begin{array}{c}
    p \equiv 1 \;(mod \; 4) \quad y \quad p \equiv 1 \;(mod \; 8) \\
    \\
    p \equiv 3 \;(mod \; 4)\quad y \quad p \equiv 3 \;(mod \; 8)
    \end{array} \)
En el primer caso, 2 y p-1 son residuos cuadráticos módulo p y tendremos (30) :
    \(\begin{array}{c}
    2^{(p-1)/2}\equiv 1 \;(mod \; p) \Rightarrow 2^{(p+1)/2}- 2\equiv 0 \;(mod \; p) \\
    \\
    (p-1)^{(p-1)/2}\equiv 1 \;(mod \; p) \Rightarrow (p-1)^{(p+1)/2}+ 1\equiv 0 \;(mod \; p)
    \end{array} \)
Multiplicando la última ecuación por 2 y sumándole el resultado superior, nos queda (31) :
    \(2(p-1)^{\frac{p+1}{2}}+ 2 ^{\frac{p+1}{2}} \equiv 0 \;(mod \; p) \rightarrow 2\left(\frac{p-1}{2}\right)^{\frac{p+1}{2}} + 1 \equiv 0 (mod \; p)
    \)
En el segundo caso, 2 y p-1 son NO residuos cuadráticos módulo p y se llega al mismo resultado.

TEOREMA

Si p es un primo que tiene distinto módulo respecto a 4 y a 8, entonces se cumple (32) :
    \(\displaystyle 2\left(\frac{p-1}{2}\right)^{\frac{p+1}{2}} - 1 \equiv 0 (mod \; p) \)
Demostración

Sólo podemos tener (33) :
    \( \begin{array}{c}
    p \equiv 1 \;(mod \; 4) \quad y \quad p \equiv 5 \;(mod \; 8) \\
    \\
    p \equiv 3 \;(mod \; 4)\quad y \quad p \equiv 7 \;(mod \; 8)
    \end{array} \)
Pues, en otros casos, como por ejemplo con los restos 1 y 3, se tendría (34) :
    \(\left.
    \begin{array}{l}
    p = 4x+1 \Rightarrow 2p = 8x+2 \\
    \\
    p = 8y+3 \Rightarrow p = 8y+3 \\
    \end{array}
    \right\}\; \Rightarrow p = 8(x-y)-1 = 8z+7 \)
lo cual es, claramente, incompatible.

Así pues, En el primero de los casos válidos, tendremos que 2 NO es residuo cuadrático módulo p y p-1 SI es residuo cuadrático módulo p y tendremos (35) :
    \(\begin{array}{c}
    2^{(p-1)/2}\equiv -1 \;(mod \; p) \Rightarrow 2^{(p+1)/2}+ 2\equiv 0 \;(mod \; p) \\
    \\
    (p-1)^{(p-1)/2}\equiv 1 \;(mod \; p) \Rightarrow (p-1)^{(p+1)/2}+ 1\equiv 0 \;(mod \; p)
    \end{array} \)
Multiplicando la última ecuación por 2 y restándole el resultado superior, nos queda (36) :
    \(2(p-1)^{\frac{p+1}{2}}- 2 ^{\frac{p+1}{2}} \equiv 0 \;(mod \; p) \rightarrow 2\left(\frac{p-1}{2}\right)^{\frac{p+1}{2}} - 1 \equiv 0 (mod \; p)
    \)
En el segundo de los casos válidos, tendremos que 2 SI es residuo cuadrático módulo p y p-1 NO es residuo cuadrático módulo p y se llega al mismo resultado que el visto.

TEOREMA

Para todo entero positivo \(a\) y todo primo p, tales que (a,p) = 1, se cumple (37) :
    \([-a]^{a-1}[p-a]^{p-a} - 1\equiv 0 \;(mod \; p)
    \)
Demostración

Según el teorema de Euler Fermat tenemos (38) :
    \([p-a]^{p-1} - 1\equiv 0 \;(mod \; p) \)
y operando (39) :
    \([p-a]^{a-1}[p-a]^{p-a} - 1\equiv 0 \;(mod \; p) \)
pero el factor de la izquierda puede desarrollarse según el teorema del binomio para dar (40) :
    \( [p-a]^{p-1} = a·p + [-a]^{p-1}\)
y sustituyendo (41) :
    \(\begin{array}{l}
    \left[a·p + [-a]^{p-1}\right][p-a]^{p-a}- 1\equiv 0 \;(mod \; p)\Rightarrow \\
    \\
    \Rightarrow [-a]^{a-1}[p-a]^{p-a} - 1\equiv 0 \;(mod \; p)
    \end{array} \)
En particular, haciendo \(a=2\) (42):
    \(2[p-2]^{p-2}+ 1 \equiv 0 \;(mod \; p) \)
y poniendo p-2 = q, con q primo (43) :
    \(2·q^q+ 1 \equiv 0 \;(mod \; p) \)
siendo p y q (p > q) primos gemelos.

También puede obtenerse sin dificultad la relación (44) :
    \(q^q - 8 \equiv 0 \;(mod \; p) \)
siendo p y q (p < q) primos gemelos.

TEOREMA

Toda expresión de la forma (45) :
    \(4·a^{4x} + m^4b^{4y}\)
es un número compuesto. Además, si a, b y m son tales que (a,5) = (b,5) = (m,5) = 1, uno de los factores resultantes es múltiplo de 5.

Demostración.

Es suficiente con desarrollar la expresión (46) :
    \(\left(2·a^{2x} + m^2b^{2y}\right)^2 - (2·ma^xb^y)^2 \)
Cuyo desarrollo nos da el valor del enunciado, pero de la que sabemos que se puede poner en la forma (47) :
    \( \left(2a^{2x} + m^2b^{2y} + 2ma^xb^y \right)\left(2a^{2x} + m^2b^{2y} - 2ma^xb^y \right)\)
Recordando, además, que \(4 \equiv -1 \;(mod \; 5)\) , tendremos (48) :
    \(4a^{4x} + m^4b^{4y}= \left(mb^y\right)^4 -\left(a^x\right)^4 \)
y si se cumple (a,5) = (b,5) = (m,5) = 1, según el teorema de Euler Fermat, la expresión anterior es múltiplo de 5.
Los números de la forma (49) :
    \(4a^{4x} + 1 y 2^{4x+2} + 1 \)
son subconjuntos de (45).

TEOREMA

Si p es un primo de la forma \(p = 2n+1\), entonces p divide a\(2·n^{n+1} + 1\) sí \(n \equiv 0 \;;\; 1 (mod \; 4)\) y p divide a \(2·n^{n+1} - 1\) sí\(n \equiv 2 \;;\; 3 (mod \; 4)\).
Así mismo, si p es un primo de la forma \(p = 2n-1\), entonces p divide a\(2·n^n - 1\) sí\(n \equiv 0 \;;\; 1 (mod \; 4)\) y p divide a \(2·n^n + 1\) sí\(n \equiv 2 \;;\; 3 (mod \; 4)\).

Demostración.

Podemos considerar las siguientes equivalencias (50) :
    \(\begin{array}{c}
    Si\; p= 2n+1 \Rightarrow 2n^{n+1}\pm 1 = 2 \left(\frac{p-1}{2}\right)^{\frac{p-1}{2}} \pm 1 \\
     \\
    Si\; p= 2n-1 \Rightarrow 2n^n \pm 1 = 2 \left(\frac{p+1}{2}\right)^{\frac{p+1}{2}} \pm 1
    \end{array} \)
que, junto con las restricciones modulares impuestas, nos permiten ver que lo expuesto en el desarrollo de las ecuaciones (22), (25), (28) y (32) nos lleva a la demostración de lo planteado.

TEOREMA

Si q = 4n + 1 es primo, entonces\(4·n^{n+1} + 1\) es múltiplo de q.

Demostración.

Si n es impar, podemos escribir (51) :
    \((4n)^n + 1 \equiv 0 \;(mod \; q)\Rightarrow 4^nn^n + 1 \equiv 0 \;(mod \; q) \)
pero tenemos (52) :
    \(q = 4n+1 = 4(2m-1)+1 = 8m-3\)
Por lo tanto, 2 es un NO residuo cuadrático módulo q y se cumplirá (53) :
    \(2^{(q-1)/2n}\equiv -1 \;(mod \; q)\Rightarrow 2^{2n} + 1 = 4^n + 1 \equiv 0 \;(mod \; q) \)
por lo qué sustituyendo en (51), tendremos (54) :
    \(-1·n^n + 1\equiv 0 \;(mod \; q) \)
Por otro lado, por definición (55) :
    \(4n\equiv -1 \;(mod \; q) \)
y, por lo tanto (56) :
    \(-1·n^n + 1 = 4n·n^n + 1 = 4n^{n+1} + 1\equiv 0 \;(mod \; q) \)
Si n es par tenemos (57) :
    \((4n)^n - 1 \equiv 0 \;(mod \; q) \Rightarrow 4^nn^n - 1 \equiv 0 \;(mod \; q) \)
pero, en este caso (58) :
    \(q = 4n+1 = 4(2m) + 1 = 8m + 1\)
y, por lo tanto, 2 es residuo cuadrático módulo q y tendremos (59) :
    \( 2^{(q-1)/2n}\equiv -1 \;(mod \; q)\Rightarrow 4^n\equiv 1 \;(mod \; q)
    \)
Con lo cual, sustituyendo en (57) y teniendo en cuenta (55), resulta (60) :
    \( -4n·n^n - 1 \equiv 0 \;(mod \; q) \Rightarrow 4·n^{n+1}+ 1 \equiv 0 \;(mod \; q)\)
y queda demostrado lo que nos proponíamos.

BIBLIOGRAFIA

1.- Apóstol, T.M. Introducción a la teoría analítica de números. Ed. Reverté.
2.- Aparicio, E., Teoría de los Números, Servicio Editorial U.P.V.
3.- A. Vera Lopez y R. Esteban Romero. Problemas de matemática discreta, Ed A.V.L.
4.- J. A. Hervás. Criterios de Divisibilidad.
5.- Cilleruelo, J. ; Córdoba, A., La teoría de los Números, Biblioteca Mondadori.
6.- J. A. Hervás, Aplicaciones de los residuos cuadráticos.
Te han sido de utilidad estos apuntes sobre la factorización y divisibilidad de ciertas expresiones numéricas?.- Recomiénda esta página!

Otros usuarios de Matemáticas y poesía también han visto:


 


tema escrito por: José Antonio Hervás