Introducción

El propósito de este material es poner a disposición de los profesores del nivel medio superior una breve exposición del tema de CONGRUENCIAS y una selección de problemas de concurso a todos los niveles: Estatal, nacional (diversos países) y de Olimpiadas Internacionales.

Este tema de la teoría de los números no es parte de la currícula de Bachillerato en nuestro estado, sin embargo es tema de exámenes en concursos nacionales e internacionales, razón por la cual tenemos que incluirlo en los materiales para preparar a nuestros estudiantes para las Olimpiadas Estatales y Nacionales.

Ha sido una tradición proporcionar a los estudiantes que participan en nuestro estado en la Olimpiada de Matemáticas, una exposición de esta temática en los talleres de entrenamiento.

Creemos que este tipo de materiales, en manos de profesores entusiastas, contribuirá a una mejor preparación de nuestros representantes en las olimpiadas nacionales.

Eduardo Tellechea Armenta

Profesor del Departamento de Matemáticas

Universidad de Sonora.

Octubre de 1998.

C O N G R U E N C I A S

Con el fin de motivar el concepto de CONGRUENCIA, analizaremos los siguientes dos problemas.

Problema 1. Se tiene un edificio de dos pisos con los cuartos numerados como en la figura

¿En que piso localizamos el cuarto No. 98 ?

Solución: En la planta baja (Ad.), pues claramente observamos que en el primer piso están los cuartos con números impares y en la planta baja, los de números pares.

Problema 2. Se tiene un edificio de cinco pisos con los cuartos numerados como en la figura.

¿En que piso localizamos el cuarto No. 98?

Solución: En el problema anterior, por su sencillez, pudimos mentalmente dividir al conjunto de los enteros (positivos) en dos clases ajenas: pares e impares. En este segundo problema tenemos que dividirlos en 5 clases ajenas y ser capaces de ubicar a cualquier entero en alguna de ellas.

Si observamos detenidamente la figura, podemos ubicar a los cuartos de la siguiente manera: 

No. de Piso            Característica                                                                       Forma

Primer piso:             Múltiplos de 5                                                                            5k

Segundo piso:          Los que exceden en una unidad a un múltiplo de 5                    5k+1

Tercer piso:             Los que exceden en dos unidades a un múltiplo de 5                 5k+2

Cuarto piso:            Los que exceden en tres unidades a un múltiplo de 5                 5k+3

Quinto piso: Los que exceden en cuatro unidades a un múltiplo de 5                        5k+4.

Después de este pequeño análisis, podemos decir que el cuarto No. 98 se encuentra en el cuarto piso,

puesto que 98 = 5(19) + 3.

Obsérvese que los del primer piso son aquellos que al dividirse entre 5 dejan residuo cero, los del segundo piso son aquellos que al dividirse entre 5 dejan residuo 1 y así sucesivamente.

Si consideramos el conjunto de los enteros, con este criterio podemos dividirlos en 5 clases:

C₀ = {…, -15, -10, -5, 0, 5, 10, 15, …}

C₁ = {…, -14, -9, -4, 1, 6, 11, 16, …}

C₂ = {…, -13, -8, -3, 2, 7, 12, 17, …}

C₃ = {…, -12, -7, -2, 3, 8, 13, 18, …}

C₄= {…, -11, -6, -1, 4, 9, 14, 119, …}.

La característica de la clase C_r es que al dividirse cualquiera de sus elementos entre cinco, deja residuo r. 

Si dos enteros pertenecen a la misma clase, diremos que ellos son congruentes módulo 4. 

En general tenemos la siguiente definición:

DEFINICIÓN.- Decimos que los enteros a y b son CONGRUENTES MÓDULO m , m>0 si al dividirse entre m dejan el mismo residuo, y lo denotaremos como:

ab (mod _m)

Ejemplos. -13 17 (mod ₅) pues ambos pertenecen a C₂.

5 15 (mod ₅) pues ambos pertenecen a C₀

8 17 (mod ₃) pues al dividirse entre 3, dejan residuo 2.

PROPOSICIÓN.- ab (mod _m) Û m | (b-a).

Demostración:

a) (Þ)

Si a = mq₁ + r y b = mq₂ + r con 0 £ r < m Þ b-a = m(q₂ - q₁) Þ m | (b-a).

b) (Ü)

m | (b-a) Þ b-a = mk para algún entero k

Por el algoritmo de la división a = mq₁ + r₁ y b = mq₂ + r₂ con 0 £ r₁ < m , 0 £ r₁ < m

restando estas igualdades obtenemos:

b-a = m(q₂ - q₁) + (r₂ - r₁). Pero como b-a = mk , tenemos que r₂ - r₁ = 0 y por lo tanto r₂ = r_..

por lo que ab (mod _m)

 Teorema: La relación congruencia módulo m tiene las siguientes propiedades:

a) aa (mod _m)

b) Si ab (mod _m) entonces ba (mod _m)

c) Si ab (mod _m) y bc (mod _m) entonces ac (mod _m)

Demostración: Sólo demostraremos 3), dejando al lector el resto, como ejercicio.

Como ab (mod _m), se tiene que m | (b-a), es decir b-a = mk (*)

Análogamente como bc (mod _m) tenemos que m | (c-b), es decir c-b = mp (**)

Sumando (*) y (**) tenemos que c-a = (b-a) + (c-b) = mk - mp = mh

lo cual significa que ac (mod _m).

Es de esperarse, en vista del teorema anterior, que las congruencias se comporten en muchos aspectos como igualdades. Esta semejanza queda ilustrada en el siguiente teorema:

 Teorema: Sean a, b, c enteros y m entero positivo.

• Si ab (mod _m) entonces:

1. a) a+x b+x (mod _m) para todo entero x.

   b) ax bx (mod _m) para todo entero x

   Si ab (mod _m) y cd (mod _m), entonces:

   a) a+c b+d (mod _m)

   b) a-c b-c (mod _m)

   c) ac bd (mod _m)

   d) aⁿ bⁿ (mod _m) para todo entero positivo n

   ---

 Demostración: 1. Es inmediata y se deja como ejercicio al lector, así como 2 a) y 2 b).

Para la demostración de 2 c) procedemos aplicando 1 b) y la propiedad 3 del teorema anterior.

Si ab (mod _m) entonces acbc (mod _m)

Si cd (mod _m) entonces bcbd (mod _m)

y en consecuencia acbd (mod _m).

Problema 3. (Regla de la divisibilidad entre 9)

Demuestre que un entero N, expresado en notación decimal, es divisible entre 9 si y sólo si la suma de sus dígitos es divisible entre 9.

Solución: sea N = a₀ a₁ a₂ ... a_n-1 a_n

N = a_nx10⁰ + a_n-1 x10¹ + a_n-2x10² x ... x a₁x10^n-1 + a₀ x10ⁿ

Como

10⁰ 1 (mod ₉) Þ a_nx10⁰ a_n (mod ₉)

10¹ 1 (mod ₉) Þ a_n-1x10¹ a_n-1 (mod ₉)

10² 1 (mod ₉) Þ a_n-2x10² a_n-2 (mod ₉)

. .

. .

. .

10^n-1 1 (mod ₉) Þ a₁x10^n-1 a₁ (mod ₉)

10ⁿ 1 (mod ₉) Þ a₀ x10ⁿ a₀ (mod ₉)

Sumando término a término, obtenemos: N a₀ + a₁ + a₂ + ... + a_n-1 + a_n (mod ₉)

Lo cual significa que 9 | N Û 9 | (a₀ + a₁ + a₂ + ... + a_n-1 + a_n)

Problema 4 . (Regla de la divisibilidad entre 3)

Demuestre que un entero N, expresado en notación decimal, es divisible entre 3 si y sólo si la suma de sus dígitos es divisible entre 3.

 Solución: Se deja al lector

Problema 5. (Otra regla de la divisibilidad entre 3)

Demuestre que un entero N = abcd de cuatro cifras, expresado en notación decimal, es divisible entre 9 si y sólo si a-2b+4c+d divisible entre 9.

 Solución: Se deja al lector

 Teorema 3. Si cacb (mod _m) y (c,m) = d, de modo que m = dw, entonces ab (mod _w).

Demostración. c = dv y m = dw donde (v,w) = 1.

dw | c(a-b) y por lo tanto w | v(a-b) y como (v,w) = 1 se tiene que w | (a-b),

es decir ab (mod _w).

 Como un caso particular tenemos el siguiente resultado:

Corolario: Si cacb (mod _m) y (c,m) = 1, entonces ab (mod _m)

A continuación enunciaremos sin demostración un importante resultado de la teoría de los números, conocido como:

Teorema de Fermat. Si p es primo y no divide al entero a, entonces a^p-1 1 (mod _p).

Problema 6. Demuestre que si (n,7) = 1 entonces 7 | (n¹² – 1)

Solución: Obsérvese que no podemos aplicar directamente el teorema de Fermat pues

n^13-1 1 (mod₁₃) y lo que queremos es congruencia módulo 7.

Si (n,7) = 1 , entonces 7 no divide al entero n , y por el teorema de Fermat n^7-1 1 (mod₇)

Es decir n⁶ 1 (mod₇). Si elevamos al cuadrado en ambos miembros de la congruencia, tendremos que (n⁶ )²(1)² (mod₇), es decir n¹² 1 (mod₇), lo cual significa que 7 | (n¹² – 1).

Problema 7. Determine para que enteros positivos n, 2ⁿ –1 es divisible por 7.

Solución: Si n = 3k por lo siguiente:

a) Si n = 3k Þ 2ⁿ = (2³)^k = 8^k 1^k 1 (mod ₇) Þ 7 | (2ⁿ – 1)

b) n = 3k + 1 Þ 2ⁿ = (2³ )^k (2) = 8^k (2) 2 (mod ₇)

c) n = 3k + 2 Þ 2ⁿ 4 (mod ₇)

Problema 8. Pruebe que 2ⁿ + 1 nunca es divisible por 7.

Solución: Del ejercicio anterior se observa que para cualquier entero n, 2ⁿ 1 ó 2 ó 4 (mod ₇) y por lo tanto 2ⁿ no es congruente con –1 módulo 7 y como –1 6 (mod ₇),

2ⁿ no es congruente con 6 módulo 7 y en consecuencia 2ⁿ +1 no podrá ser congruente con 7 módulo 7.

Problema 9. Demuestre que si 7 no es un divisor de n, entonces n⁶ 1996 (mod ₇).

Solución: Por el teorema de Fermat, n⁶ 1 (mod ₇), y 11996 (mod ₇)

 Problema 10. Demuestre que para todo entero no negativo n, 17 es un divisor de

3⁴ⁿ⁺² + 2⁶ⁿ⁺³.

Solución: Para n = 0 se cumple que 3² + 2³ = 17 lo cual significa que 3² + 2³ 0 (mod₁₇)

es decir 3² -2³ (mod₁₇). Si elevamos a la potencia impar 2n + 1, obtendremos

(3² )²ⁿ⁺¹ (-2³ )²ⁿ⁺¹(mod₁₇)

3⁴ⁿ⁺² -2⁶ⁿ⁺³ (mod₁₇)

3⁴ⁿ⁺² + 2⁶ⁿ⁺³ 0 (mod₁₇)

lo cual significa que 17 es un divisor de 3⁴ⁿ⁺² + 2⁶ⁿ⁺³.

Problema 11. ( Olimpiada Nacional ) Demuestre que para todo entero no negativo n, se cumple que

(n³-n)( 5⁸ⁿ⁺⁴ + 3⁴ⁿ⁺²) es múltiplo de 3804.

Solución: Como n³-n = (n - 1)(n)(n + 1), es múltiplo de 6 y el número 5⁸ⁿ⁺⁴ + 3⁴ⁿ⁺² es par, por ser suma de impares, y 3804 = sólo restaría probar que 317 | (5⁸ⁿ⁺⁴ + 3⁴ⁿ⁺²), lo cual es completamente análogo al ejercicio No. 6 y se deja como ejercicio al lector.

Problema 12. Encuentre un número que al dividirse por 10 deja residuo 10, al dividirse por 9 deja residuo 8 y así sucesivamente hasta que al dividirse por dos deje residuo 1.

Solución: Tal número N debe cumplir lo siguiente:

N 9 (mod₁₀) pero como 9-1 (mod₁₀) Þ N -1 (mod₁₀)

N 8 (mod₉)     "       "        8-1 (mod₉) Þ N -1 (mod₉)

N 7 (mod₈)      "       "       7-1 (mod₈) Þ N -1 (mod₈)

. . .

. . .

. . .

N 1 (mod₂)     "         "      1-1(mod₂) Þ N -1 (mod₂)

De las últimas congruencias a satisfacerse por N tenemos que :

N+1 debe ser múltiplo de 2,3,4,5,6,7,8,9 y 10, siendo el menor de esos números

N+1 = (10)(9)(4)(7) = 2520 y por lo tanto el número buscado es N = 2519.

Problema 13. ( Olimpiada Internacional ) Encontrar el número natural N más pequeño que cumple las siguientes condiciones:

1. En la representación decimal, termina en 6.
2. Si el 6 es trasladado al principio del número, el resultado es 4N.

Solución: Al número N lo podemos expresar de la forma

N = 10y + 6 por ejemplo abc6 = (abc)(10) + 6

6(10^m) + y = 4(10y + 6) " " " 6abc = 6(10³) + abc = 4(abc0) + 6

6(10^m) –24 = 39y

Lo cual significa que 6(10^m) 24 (mod ₃₉).

Es decir al dividir 600...0 ( m ceros) deja residuo 39, y tal número es 600,000

 En consecuencia N = 153,846.

 Problema 14. ( Olimpiada Nacional ) Una oficina de Turismo va a realizar una encuesta sobre número de días soleados y número de días lluviosos que se dan en el año. Para ello recurre a seis regiones que le transmiten los datos de la siguiente tabla:

La persona encargada de la encuesta no es imparcial y tiene esos datos más detallados. Se da cuenta de que, prescindiendo de una de las regiones, la observación da un número de días lluviosos que es la tercera parte del de días soleados. Razonar cuál es la región de la que prescindirá.

Solución:

Al suprimir una región, la suma de días soleados o lluviosos de las restantes ha de ser múltiplo de 4. Las seis regiones suman 1994 que dividido entre 4 da resto 2. El único dato de esta columna que da resto 2 al dividirlo entre 4 es 330 correspondiente a la región F.

En términos de congruencias tenemos que:

3360 (mod ₄)

3211 (mod ₄)

3353 (mod ₄)

3433 (mod ₄)

3291 (mod ₄)

3302 (mod ₄)

________________________

199410 (mod ₄)

pero como 102 (mod ₄), tenemos que 19942 (mod ₄).

Si omitimos 330, obtendremos una cantidad congruente con 0 , lo cual significa que deja residuo 0 al dividirla entre 4.

A la congruencia 19942 (mod ₄) , le restamos la congruiencia 3302 (mod ₄), obteniendo

16640 (mod ₄)

En consecuencia, suprimiendo esta región (F) quedan entre las cinco restantes 416 días lluviosos y (3)(416) = 1248 días soleados.

Problema 15. Demuestre que si a es primo con 240 entonces 240 es un divisor de a⁴ - 1.

Solución: La factorización de 240 en primos es:

240 = (2⁴)(3)(5)

Así pues, debemos probar que 2⁴ | a⁴ – 1, 3 | a⁴ – 1, 5 | a⁴ – 1

Claramente, por el teorema de fermat, 3 | a⁴ – 1 y 5 | a⁴ – 1

Como (a, 240) = 1 y 2 es un factor de 240, 2 no puede ser un factor de a y en consecuencia

a= 2k + 1 Þ a² = 4k² + 4k + 1 es decir a² – 1 = 4k(k + 1) y como k(k + 1) es par Þ

8 | a² – 1.

Por otro lado como a es impar, a² también es impar y por lo tanto a² +1 es par

8 | a² – 1 y 2 | a² – 1 Þ 2⁴ | a⁴ – 1.

 Problema 16. ( Concurso Estatal ) Sean x, y , z números enteros tales que x³ +y³ - z³ es múltiplo de 7. Demuestre que uno de ellos es múltiplo de 7.

Solución: Todo número es de alguna de las siguientes formas: 7k, 7k1, 7k2, 7k3 y como:

(7k1)³ = (7k)³ + … +( 1)³

(7k2)³ = (7k)³ + … +( 2)³ = [(7k)³ + … 7] 1

(7k3)³ = (7k)³ + … +( 3)³ = [(7k)³ + … 28] 1

se tiene que los residuos posibles al dividir entre 7 el cubo de un número son 0, 1, ó -1.

Si por el contrario se tiene que ninguno es múltiplo de 7, entonces

x³ 1 (mod ₇)

y³ 1 (mod ₇)

z³ 1 (mod ₇)

Por lo tanto x³ +y³ - z³ nunca podrá ser congruente con 0 módulo 7, pues con ninguna combinación en la suma de tres números del conjunto {} se puede tener suma igual a 0.

Problema 17. ( Concurso Nacional ) Pruebe que n^n-1 -1 es divisible por (n-1)² para todo entero n > 1.

Solución:

n^n-1 -1 = (n-1) (n^n-2 + n^n-3 + … + n + 1)

Como n 1 (mod _n-1), se tiene que n^k 1 (mod _n-1), para todo entero positivo k.

Así (n^n-2 + n^n-3 + … + n + 1) 1 + 1 + … + 1 n-1 (mod _n-1)

y por lo tanto, (n-1)² divide a n^n-1 -1.

Problema 18. Justifique, utilizando congruencias, el procedimiento descrito a continuación para adivinar un número.

Diga a alguien que seleccione un número entero menor que 1000, que lo divida entre 7, 11 y 13 y proporcione los tres residuos de la división. Usted podrá entonces decirle que número seleccionó originalmente. Esto se hace multiplicando los tres residuos respectivamente por los "números mágicos" 715, 364 y 924, sumando los productos resultantes y restando de la suma el mayor múltiplo de 1001 que deje una diferencia positiva. Esta diferencia es el número seleccionado.

Ejemplo: Si el número en cuestión es 523, los residuos son 5,6 y 3 respectivamente y usted escribiría:

715*15 = 3575

364*6 = 2184

924*3 = 2772

              8531

El múltiplo de 1001 más cercano menor que 8531 es el 8008 y al restarlos obtenemos 523.

Solución: Sea x el número desconocido seleccionado, a, b y c los respectivos residuos cuando x es dividido entre 7, 11 y 13 respectivamente, entonces:

xa (mod ₇) y 715x(715)a (mod ₇)

xb (mod ₁₁) y 364x(364)b (mod ₁₁)

xc (mod ₁₃) y 924x(924)a (mod ₁₃)

restando de ambos miembros de cada congruencia, tenemos

715(x-a)0 (mod ₇) (1)

364(x-b)0 (mod ₁₁) (2)

924(x-c)0 (mod ₁₃) (3)

Como la congruencia (1) es divisible por 11 y 13 y en consecuencia por 11, 13 y 7, ó por 1001 (1001 = 7*11*13).

Análogamente las congruencias (2) y (3) también son divisibles por 1001 y sumando, tendremos

2003x - (715a +364b + 924c) 0 (mod ₁₀₀₁)

ó equivalentemente

2003x 715a +364b + 924c (mod ₁₀₀₁)

pero como

2003x x (mod ₁₀₀₁)

tenemos que

x 715a +364b + 924c (mod ₁₀₀₁)

Así pues, como pedimos que x < 1000, x dejará residuo x al dividirse entre 1001 y

715a +364b + 924c también dejará residuo x al dividirse entre 1001.

B I B L I O G R A F Í A

1. Olimpiadas de Matemáticas: 140 Problemas, seis años de éxitos.

Varios autores

2. Recreations in The Theory of Numbers, The Queen of Mathematics Entertains.

Autor: Albert H. Beiler

• Dover Publications, Inc, New York 1966

 3. Folletos de Problemas para las Olimpiadas Mexicanas de Matemáticas.

Varios autores

• Sociedad Matemática Mexicana- Academia de la Investigación Científica.

 4. Problemario hacia la XI Olimpiada Mexicana de Matemáticas, Sonora 1997.

Autores:

Enrique Hugues Galindo

Miguel Angel Moreno Núñez

Eduardo Tellechea Armenta.

• Universidad de Sonora, Marzo de 1997.

5. Soluciones al Problemario hacia la XI Olimpiada Mexicana de Matemáticas.

Autores.

Enrique Hugues Galindo

Miguel Angel Moreno Núñez

Carlos Alberto Robles Corbalá

Eduardo Tellechea Armenta.