Clase 1 - Congruencias

Esperamos sus mails en misc@oma.org.ar

La noción de congruencias es muy útil a la hora de trabajar con restos en la división por un número m, pues nos da una forma simple y ordenada de trabajar con el conjunto de los enteros.

Decimos que dos números enteros a y b son congruentes módulo m (donde m es natural) si a y b tienen el mismo resto en la división por m. Escribimos a = b mód(m) para simbolizar que a es congruente a b módulo m.

Veamos algunos ejemplos:

• 1 = 6 mód(5) porque 6 y 1 tienen el mismo resto en la división por 5.
• 11 = -1 mód(4) pues 11 y -1 tienen el mismo resto en la división por 4.
• 14 = 0 mód(2) porque ambos tienen resto 0 en la división por 2 (es decir son divisibles por 2).

Lo interesante de esto es que podemos dividir a los números enteros en varios grupos según el resto que tengan en la división por un número natural m. Por ejemplo, según el resto en la división por 3:

A = {...., -6, -3, 0, 3, 6, 9, 12, ....}

B = {...., -5, -2, 1, 4, 7, 10, 13, ...}

C = {...., -7, -4, -1, 2, 5, 8, 11, ....}

El conjunto de los enteros que tienen resto 2 en la división por 3 (..., -7, -4, -1, 2, 5, 8,....), son todos los x enteros tal que x = 2 mód(3). Otra forma de escribir esto mismo, de mucha utilidad a la hora de resolver problemas, es decir que son los enteros de la forma 3k+2 donde k es entero.

Un resultado muy útil que pueden verificar ustedes mismos es que a = b mód(m) si y sólo si a-b es divisible por m.

Este resultado es uno más en una larga lista de propiedades que cumple la congruencia y que comparte con la igualdad.

• Si a = b mód(m) y b = c mód(m) entonces a = c mód(m)

Esta propiedad es casi obvia pues si a tiene el mismo resto en la división por m que b, y b el mismo que c, entonces a y c tendrán el mismo resto en la división por m. Es muy importante que en ambos casos se trate del mismo m.

• Si a = b mód(m) y c = d mód(m) entonces:

a) a + c = b + d mód(m)
b) a - c = b - d mód(m)
c) a.c = b.d mód(m)

a) Como a = b mód(m) entonces m | a-b (que significa m divide a a-b). Del mismo modo m | c-d. Como m divide a a-b y a c-d entonces dividirá a la suma de ambos números. Es decir, m | a-b+c-d, o lo que es lo mismo m | (a+c)-(b+d) lo que implica que a + c = b + d mód(m).

b) Se demuestra igual al anterior.

c) Sean a = m.e + r₁ , b = m.f + r₁ , c = m.g + r₂ y d = m.h + r₂ donde 0 < r₁, r₂ < m. Notar que a y b tienen el mismo resto en la división por m, al igual que c y d. Entonces a.c = (m.e + r₁).(m.g + r₂) = m (m.e.g + e.r₂ + g.r₁) + r₁.r₂. Entonces a.c = r₁.r₂ mód(m). Del mismo modo b.d = r₁.r₂ mód(m) por lo que a.c = b.d mód(m).

• Si a = b mód(m) entonces aⁿ = bⁿ mód(m)

Intenten probarlo ustedes mismos utilizando el punto anterior.

• Si a.b = a.c mód(m) y m es coprimo con a (es decir que a y m no tienen ningún divisor primo en común), entonces b = c mód(m).

Como a.b = a.c mód(m) entonces m | a.b-a.c. Es decir que m | a(b-c). Dado que ningún divisor de m divide a a, entonces m debe dividir a b-c con lo cual tenemos que b = c mód(m).

• Si a.b = 0 mód(p) donde p es primo, entonces a = 0 mód(p) ó b = 0 mód(p).

Les dejamos a ustedes la demostración de esta propiedad. Cualquier duda consúltennos.

Debido a las frecuentes confusiones que se generan entre estas propiedades y las propiedades de la igualdad, queremos hacerles algunas aclaraciones. Salvo casos particulares, en general NO es cierto que:

• Si a = b mód(m) y b = c mód(n) entonces a = c mód(n). Por ejemplo: 1 = 4 mód(3) y 4 = 8 mód(2) pero no es cierto que 1 = 8 mód(2).

• Si a.b = a.c mód(m) entonces b = c mód(m). Por ejemplo: 2.3 = 2.12 mód(6) pero no es cierto que 3 = 12 mód(6). Es decir, NO vale dividir en congruencias.

• Si aⁿ = bⁿ mód(m) entonces a = b mód(m). Por ejemplo: 1⁴ = 3⁴ mód(8) pero no es cierto que 1 = 3 mód(8). Es decir, NO vale sacar raíces en congruencias.

Un resultado importante:

Todo número entero a, es congruente a uno y sólo un entero r tal que 0 < r < m. Este número r es el resto de la división de a por m.

Otra forma de escribir el teorema anterior es la siguiente:

Existen únicos enteros b y r tal que a = m.b + r donde 0 < r < m.

Se pueden hallar muchísimos ejemplos donde aplicar congruencias a la resolución de problemas. Un ejemplo de esto es la deducción de criterios de divisibilidad. En la clase 2 del año pasado vimos el criterio de divisibilidad por 9, veamos ahora una criterio para el 11.

El resto al dividir un número natural N por 11, es igual al resto de dividir la suma alternada de sus cifras por 11.

Veamos por qué. Sea N = a₀ + a₁.10 + a₂.10² + ... + a_n.10ⁿ

Como 10 = -1 mód(11) entonces 10^k = (-1)^k mód(11) para cualquier natural k. Por tanto:

N = a₀ + a₁.(-1) + a₂.(-1)² + ... + a_n.(-1)ⁿ mód(11). Es decir que N y a₀ - a₁ + a₂ - ... + a_n.(-1)ⁿ tienen el mismo resto en la división por 11.

Por ejemplo, 297424 = 4-2+4-7+9-2 mód(11) por lo que 297424 tiene resto 6 en la división por 11.

Un resultado interesante que se desprende de esta demostración es que:

Un número es divisible por 11 si y sólo si la suma alternada de sus cifras es divisible por 11.

Veamos algunos problemas para ver como aplicar congruencias. Antes de leer las respuestas les sugerimos que intenten resolverlos por cuenta propia ...

A. Hallar un criterio de divisibilidad para el 7 y uno para el 13.

B. Probar que la ecuación 5ⁿ + 2 = 17^m no tiene soluciones con n y m naturales.

Soluciones

A. El objetivo de hacer un criterio de divisibilidad por m es evitar realizar la división de un número grande por m. La idea es hacer alguna operación con el número que involucre solamente sumas o restas de modo de obtener un número más chico y con el mismo resto en la división por m. Luego se repite este proceso hasta llegar a un punto en el que se obtiene un número pequeño (o relativamente pequeño) del que se obtiene el resto en la división por m, haciendo la división misma. Esto es especialmente útil en computación ya que una computadora suma y resta mucho más rápido de lo que divide.

Lo más interesante es que se puede hallar un criterio de divisibilidad para cualquier natural m (lo cual no siempre es fácil, ni siempre es útil).

Veamos un criterio de divisibilidad que sirva tanto para el 7 como para el 13. La primer idea es notar que 1001 es divisible por 7 y por 13 (ya que 1001 = 7.11.13). Dado que 1000 = -1 mód(1001) entonces 1000^k = (-1)^k mód(1001). ¿Se les ocurre como seguir en base a lo que vimos sobre el criterio de divisibilidad por 11?

Si N = a_n a_n-1 ..... a₆ a₅ a₄ a₃ a₂ a₁ a₀ donde a₀ es el dígito de las unidades, a₁ el de las decenas, etc. Otra forma de escribir esto es: N = a₂ a₁ a₀ + 1000 . a₅ a₄ a₃ + 1000² a₈ a₇ a₆ + ....

Entonces a₂ a₁ a₀ = (-1)⁰ a₂ a₁ a₀ mód(1001), 1000 . a₅ a₄ a₃ = (-1)¹ . a₅ a₄ a₃ mód(1001), etc. Por lo tanto: N = a₂ a₁ a₀ - a₅ a₄ a₃ + a₈ a₇ a₆ - a₁₁ a₁₀ a₉ +.... mód(1001)

Veamos un ejemplo:

Hallar el resto al dividir N = 3932089562389214 por 13. Sabemos que N tiene el mismo resto en la división por 1001 que 214-389+562-089+932-3 = 1227. Es decir que N = 1227 mód(1001) y además 1227 = 227-1 mód(1001).

Por tanto, N = 226 mód(1001). Entonces N-226 es divisible por 1001 y por tanto en divisible por 13. Es decir que 13| N-226, lo cual equivale a N = 226 mód(13). Dado que 226 = 5 mód(13) entonces N = 5 mód(13).

O sea que el mecanismo para hallar el resto al dividir N por 13 (o por 7 que es lo mismo) es el siguiente:

• Hacer la suma alternada de los bloques de números de tres cifras comenzando por la derecha del número. Si aparecen ceros considerar al número como de dos cifras, una o cero según corresponda (como en el ejemplo restamos 089). Si la cantidad de dígitos no es múltiplo de 3 no importa, resta o sumar (según corresponda) el número de una o dos cifras (como en el ejemplo que restamos 3).
• Si se obtiene un número negativo suma un múltiplo de 1001 hasta obtener un número positivo.
• Repetir los pasos anteriores las veces que sea necesario hasta obtener un número entre 0 y 1000 ambos inclusive.
• Hallar el resto al dividir este último número por 13. Este resto será el resto al dividir N por 13.

¿Se animan a hallar un criterio de divisibilidad por 7 teniendo en cuenta que 7 divide a 999.999?¿Sirve también para el 13?

B. Encarar este problema sin conocer un poco de congruencias, podría parecer en un principio desbordante. ¿Cómo hago para saber si existen n y m si hay infinitas posibilidades para cada uno? ¿Será que de un lado obtengo siempre un número par y del otro lado siempre un impar? Esto último no ocurre, pero si ocurriera sería una buena demostración de que no existen n y m. ¿Será que el miembro de la izquierda nunca es divisible por 17? Falso también, por ejemplo si n = 14. A propósito, ¿cómo pueden probar que 5¹⁴ + 2 es divisible por 17?

Veamos como las congruencias nos facilitan las cosas. Sabemos que 5 = 1 mód(4) por lo que 5ⁿ = 1ⁿ mód(4). Entonces 5ⁿ + 2 = 1+2 mód(4). Por el otro lado, al ser 17 = 1 mód(4) tenemos que 17^m = 1^m mód(4). Y dado que 1 y 3 no tienen la misma congruencia módulo 4 ambos miembros nunca pueden ser iguales. En otras palabras no existen n y m naturales que satisfagan la ecuación del enunciado.

Les dejamos algunos problemas para que practiquen y retomamos el tema la clase que viene....

Problemas

1. Hallar todas las soluciones de la ecuación 3ⁿ - 5^m = 4 para n y m enteros positivos.

2. Hallar la cifra de las unidades de 77⁷⁷.

3. Hallar el dígito k para que el número 34512k8675423 sea divisible por 7.

4. Demostrar el siguiente resultado:

Sea p un número primo. Hallar un criterio de divisibilidad por p de modo de asegurarse que no sea necesario efectuar la división de ningún número de más de p-1 cifras.

Esta fue la primer clase de Miscelánea 2001, el curso de matemáticas por Internet. Esperamos que les haya gustado. En quince días, ofreceremos una nueva clase.

Ahora, es el turno de ustedes. Queremos que hagan los problemas y ejercicios que fuimos dando a lo largo de la clase. Cuéntennos lo que consiguieron y pregunten lo que no les salió. Envíen sus preguntas, dudas, sugerencias, experiencias y propuestas. Nuestra dirección es misc@oma.org.ar .

También nos gustaría saber tu opinión sobre esta clase. Te pedimos que te tomes unos instantes y contestes estas preguntas. Con tu ayuda podremos hacer un curso cada vez mejor.

Miscelánea OmaNet	Internet vía OmaNet    www.oma.org.ar/omanet | omanet@oma.org.ar
mensajes webmaster@oma.org.ar