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ⁿ ± bⁿ     ;     a·bⁿ + 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):

a·b^x + k  ≡ 0 (mod p)    ;     a·b^y + k ≡ 0 (mod p)

Restando una expresión de la otra tenemos (4):

a·b^x[b^y-x - 1] ≡ 0 (mod p)

En general, a.b^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):



Cuya solución, cuando (ind_g b , p-1) = 1, viene dada por [2] (6) :



donde φ(·) es la función de Euler.

EJEMPLOS

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

Tomando índices [1] para cada valor, resulta (8) :

14 + 5x ≡ 8 (mod 16) ⇒ 5x ≡ - 6 (mod 16)

2 4 + 20x ≡ 15 (mod 30) ⇒ 20x ≡ - 9(mod 30)

18 + 5x ≡ 23 (mod 46) ⇒ x ≡ 5(mod 46)

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 ⇒ (y = 1) ⇒ 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 :

16·y₁ + 2 = 46·y₂ + 5 ⇒ 16·y₁ - 46·y₂ = 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ⁿ + k es múltiplo de un primo p, entonces (10) :



para cualquier valor natural de m.

Demostración

Según el teorema de Euler Fermat, se cumple (11) :



y, a partir de ahí (12) :



pero, teniendo en cuenta (9) resulta (13) :



En particular, si a.b + k = p , tenemos (14) :



Para la segunda ecuación de (10) el resultado es trivial (15) :



Por ejemplo, para el primo 3, tenemos (16) :

a ≡ 2 (mod 3)   ;    b ≡ 1 (mod 3)   ;    k ≡ 1 (mod 3)   ⇒    a·b^m + k ≡ 0 (mod 3)
a ≡ 1 (mod 3)   ;    b ≡ 1 (mod 3)   ;    k ≡ 2 (mod 3)   ⇒    a·b^m + k ≡ 0 (mod 3)
a ≡ 1 (mod 3)   ;    b ≡ 2 (mod 3)   ;    k ≡ 1 (mod 3)   ⇒    a·b^2m+1 + k ≡ 0 (mod 3)
a ≡ 2 (mod 3)   ;    b ≡ 2 (mod 3)   ;    k ≡ 1 (mod 3)   ⇒    a·b^2m + k ≡ 0 (mod 3)
a ≡ 1 (mod 3)   ;    b ≡ 2 (mod 3)   ;    k ≡ 2 (mod 3)   ⇒    a·b^2m+1 + k ≡ 0 (mod 3)
a ≡ 1 (mod 3)   ;    b ≡ 1 (mod 3)   ;    k ≡ 2 (mod 3)   ⇒    a·b^2m+1 + k ≡ 0 (mod 3)

TEOREMA

Si a divide a (p-1) se cumple (17) :



Demostración

Por el teorema del binomio y el teorema de Euler Fermat, sabemos que se cumple (18):



Y sumando ambas expresiones, también podemos poner (19) :



y, puesto que a divide a p-1, resulta (20) :



En particular, 2 siempre divide a p-1 y, por lo tanto (21) :



TEOREMA

Para todo primo p ≡ ± 3 (mod 8) se cumple (22) :



Demostración

Para todo primo p ≡ ± 3 (mod 8), 2 es NO residuo cuadrático y se cumple (23) :



Además, p+1 siempre es residuo cuadrático módulo p y tendremos (24) :



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) :



Demostración

Para todo primo p ≡ ± 1 (mod 8), 2 es residuo cuadrático y se cumple (26) :



Además, p+1 siempre es residuo cuadrático módulo p y tendremos (27) :



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) :



Demostración

Sólo podemos tener (29) :



En el primer caso, 2 y p-1 son residuos cuadráticos módulo p y tendremos (30) :



Multiplicando la última ecuación por 2 y sumándole el resultado superior, nos queda (31) :



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) :



Demostración

Sólo podemos tener (33) :



Pues, en otros casos, como por ejemplo con los restos 1 y 3, se tendría (34) :



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) :



Multiplicando la última ecuación por 2 y restándole el resultado superior, nos queda (36) :



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) :



Demostración

Según el teorema de Euler Fermat tenemos (38) :



y operando (39) :



pero el factor de la izquierda puede desarrollarse según el teorema del binomio para dar (40) :



y sustituyendo (41) :



En particular, haciendo a = 2 (42):



y poniendo p-2 = q, con q primo (43) :



siendo p y q (p > q) primos gemelos.

También puede obtenerse sin dificultad la relación (44) :



siendo p y q (p < q) primos gemelos.

TEOREMA

Toda expresión de la forma (45) :



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) :



Cuyo desarrollo nos da el valor del enunciado, pero de la que sabemos que se puede poner en la forma (47) :



Recordando, además, que 4 = -1 (mod 5), tendremos (48) :



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) :



son subconjuntos de (45).

TEOREMA

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

Demostración.

Podemos considerar las siguientes equivalencias (50) :



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.

EJEMPLOS DE CRITERIOS DE DIVISIBILIDAD.

2x04 - 1 = 07 → 04 ( 0 (mod 4) → 2x044 - 1 múltiplo de 7
2x07 - 1 = 13 → 07 ( 3 (mod 4) → 2x777 + 1 múltiplo de 13
2x09 - 1 = 17 → 09 ( 1 (mod 4) → 2x099 - 1 múltiplo de 17
2x10 - 1 = 19 → 10 ( 2 (mod 4) → 2x1010 + 1 múltiplo de 19
2x3 + 1 = 07 → 3 ( 3 (mod 4) → 2x34 - 1 múltiplo de 07
2x5 + 1 = 11 → 5 ( 1 (mod 4) → 2x56 + 1 múltiplo de 11
2x6 + 1 = 13 → 6 ( 2 (mod 4) → 2x67 - 1 múltiplo de 13
2x8 + 1 = 17 → 8 ( 0 (mod 4) → 2x89 + 1 múltiplo de 17

TEOREMA

Si q = 4n + 1 es primo, entonces es múltiplo de q.

Demostración.

Si n es impar, podemos escribir (51) :



pero tenemos (52) :



Por lo tanto, 2 es un NO residuo cuadrático módulo q y se cumplirá (53) :



por lo qué sustituyendo en (51), tendremos (54) :



Por otro lado, por definición (55) :



y, por lo tanto (56) :



Si n es par tenemos (57) :



pero, en este caso (58) :



y, por lo tanto, 2 es residuo cuadrático módulo q y tendremos (59) :



Con lo cual, sustituyendo en (57) y teniendo en cuenta (55), resulta (60) :



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.