EJERCICIOS DE DIVISIBILIDAD Y CONGRUENCIAS

Si dos números a y b dan el mismo resto al dividirlos por m se dice que a y b son congruentes módulo m y lo escribiremos como a ≡ b (mód m).

La definición anterior es equivalente a que a ≡ b (mód m) sii a – b es divisible entre m

En este apartado manejaremos dos propiedades de las congruencias:

1.- Si a≡b (mód m) y b≡c (mód m), entonces a≡c (mód m).

2.- si a≡b (mód m) y c≡d (mód m), entonces a+c≡b+d (mód m) y ac ≡ bd (mód m)

PROBLEMA 1.-  a) Demostrar que  22222 ≡ 4 (mód m).

b) Calcula el resto de la división de 22222² entre 7.

Solución 1: a) Basta con hacer la división 22222 = 7·3174 + 4. El resto es 4.

b) Calculando: 22222² = 493817284 = 7·70545326+2. El resto es 2.

Estos  procedimientos son poco eficientes para problemas más complejos como, por ejemplo, ¿Cuál sería el resto de la división de 22222²² entre 7?, que supondría hallar el resto del cociente entre 7 de un número de alrededor de 1000 cifras. Sería mejor procedimiento utilizar las propiedades de las congruencias, así:

Solución 2: (descomponer en factores primos):

22222 = 2·41·271; es fácil ver que los factores cumplen:

2 ≡ 2 (mód 7);  41 ≡ 6 (mód 7);   271 ≡ 5 (mod 7)

Multiplicando las congruencias:

2·41·271 ≡ 2·6·5     ⇒    22222 ≡ 60 ≡ 4  (mód 7)

b) Igualmente  22222² = 2²·41²·271²;

2² ≡ 4 (mód 7); 41² ≡ 6² ≡ 1  (mód 7);  271² ≡ 5² ≡ 4 (mód 7)

22222² = 2²·41²·271² ≡ 4·1·4  = 16 ≡ 2  (mód 7)

O, más directamente, como 22222 ≡ 4  (mód 7)  ⇒   22222² ≡ 4² ≡ 2  (mód 7)

PROBLEMA 2.  Calcular el resto de la división de 22222²² entre 7.

Solución: Del problema anterior sabemos que:

22222 ≡ 4  (mód 7)

22222²² ≡ 4²² (mód 7)

Observemos que 4³ = 64 ≡ 1  (mód 7)

4³ ≡ 1  (mód 7)    ⇒   4²¹ ≡ 1 (mód 7)  y como, evidentemente,  4 ≡ 4  (mód 7),

  multiplicando ambas congruencias

4²²≡ 4  (mód 7)   ⇒    22222²² ≡ 4   (mód 7)

PROBLEMA 3. Calcular el resto de la división de 22222³³³³ entre 7.

Solución: En el problema anterior se ha obtenido:

22222 ≡ 4  (mód 7)

22222³³³³ ≡ 4³³³³ (mód 7)

Observemos que 4³ = 64 ≡ 1  (mód 7)

Como en el problema anterior: 4³ ≡ 1  (mód 7)   ⇒ 4^3·1111 ≡ 1 (mód 7)

4³³³³ ≡ 1 (mod 7) , por tanto,

4³³³³≡ 1  (mód 7)   ⇒    22222³³³³ ≡ 1   (mód 7)

El resto de la división es 1.

PROBLEMA 4.- Demostrar que  22222⁵⁵⁵⁵  + 5 es divisible por 7

Solución: Basta probar que 22222⁵⁵⁵⁵ ≡ 2  (mód 7)

En el problema anterior se ha obtenido:

22222 ≡ 4  (mód 7), por tanto:

22222⁵⁵⁵⁵≡ 4⁵⁵⁵⁵

Observemos que 4³ = 64 ≡ 1 (mód 7) y es trivial que:

4⁵⁵⁵⁵ = 4^3·1851+2  ≡ 4² ≡ 2  (mód 7)

PROBLEMA 5.-  Demostrar que  55555²²²²² ≡ 4   (mód 7)

Solución:  55555 ≡ 3   (mod 7)   ⇒  55555²²²²² ≡ 3²²²²²

Como 3² ≡ 2 (mód 7)   ⇒  3⁶ ≡ 2³    ⇒    3⁶ ≡ 1 (mód 7)

Por lo tanto, como 3⁶ ≡ 1 (mód 7):

3²²²²² = 3^{6·3703 + 4} ≡ 3⁴ ≡ 4   (mód 7)  y

55555²²²²² ≡ 3²²²²² ≡ 4   (mód 7)

PROBLEMA 6.- Demostrar que  22222⁵⁵⁵⁵⁵ + 3 es divisible por 7

Solución: Basta probar que 22222⁵⁵⁵⁵⁵ ≡ 4   (mód 7).

Como  22222 ≡ 4  (mód 7), entonces:

22222⁵⁵⁵⁵⁵ ≡ 4⁵⁵⁵⁵⁵ (mód 7)

Observemos que 4³ = 64 ≡ 1  (mód 7)

4⁵⁵⁵⁵⁵ = 4^{3·18518 +1}  ≡ 4¹ ≡ 4   (mód 7)    ⇒     22222⁵⁵⁵⁵⁵ ≡ 4   (mód 7)

Víctor Arenzana Hernández