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:

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.

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.

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 + r1 , b = m.f + r1 , c = m.g + r2 y d = m.h + r2 donde 0 < r1, r2 < 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 + r1).(m.g + r2) = m (m.e.g + e.r2 + g.r1) + r1.r2. Entonces a.c = r1.r2 mód(m). Del mismo modo b.d = r1.r2 mód(m) por lo que a.c = b.d mód(m).

Intenten probarlo ustedes mismos utilizando el punto anterior.

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

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:

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 = a0 + a1.10 + a2.102 + ... + an.10n

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

N = a0 + a1.(-1) + a2.(-1)2 + ... + an.(-1)n mód(11). Es decir que N y a0 - a1 + a2 - ... + an.(-1)n 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 5n + 2 = 17m 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 1000k = (-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 = an an-1 ..... a6 a5 a4 a3 a2 a1 a0 donde a0 es el dígito de las unidades, a1 el de las decenas, etc. Otra forma de escribir esto es: N = a2 a1 a0 + 1000 . a5 a4 a3 + 10002 a8 a7 a6 + ....

Entonces a2 a1 a0 = (-1)0 a2 a1 a0 mód(1001), 1000 . a5 a4 a3 = (-1)1 . a5 a4 a3 mód(1001), etc. Por lo tanto: N = a2 a1 a0 - a5 a4 a3 + a8 a7 a6 - a11 a10 a9 +.... 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:

¿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 514 + 2 es divisible por 17?

Veamos como las congruencias nos facilitan las cosas. Sabemos que 5 = 1 mód(4) por lo que 5n = 1n mód(4). Entonces 5n + 2 = 1+2 mód(4). Por el otro lado, al ser 17 = 1 mód(4) tenemos que 17m = 1m 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 3n - 5m = 4 para n y m enteros positivos.

2. Hallar la cifra de las unidades de 7777.

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.

¿Cuál es tu calificación general de esta clase?

Mala   Regular   Buena   Muy buena

El contenido de esta clase te resultó:

Nuevo   Conocido en parte   Conocido

Los problemas de esta clase te parecieron:

Difíciles   Regulares   Fáciles

Comentarios, preguntas, sugerencias:

Nombre y apellido (opcional):

E-mail (opcional):

    

 

Miscelánea OmaNet Internet vía OmaNet
   
www.oma.org.ar/omanet | omanet@oma.org.ar
mensajes webmaster@oma.org.ar
duty free alcohol rules duty free cigarettes prices duty free cigars online buy cosmetics online where to buy perfume buy duty free tobacco