ESTALMAT-Andaluc´ıa Sesi´on: 19

Fecha: 14/04/07

T´ıtulo: Aritm´etica modular

Actividades 06/07 Segundo Curso

Aritm´ etica modular Recordando... Divisi´ on entera (o eucl´ıdea). Divisi´ on exacta Definici´ on.- Dados dos numeros naturales a (dividendo) y b 6= 0 (divisor), llamamos divisi´on entera entre ellos a la operaci´on que consiste en encontrar otros dos n´ umeros q (cociente) y r (resto) tales que se cumpla: a = b · q + r siendo 0 ≤ r < b Se demuestra que q y r existen siempre y son u ´ nicos. Cuando el resto es nulo, r = 0, diremos que la divisi´on es exacta. M´ aximo com´ un divisor Definici´ on.- El m´aximo com´ un divisor de dos n´ umeros naturales a, b es otro n´ umero natural d tal que : 1. d|a y d|b. 2. Si e ∈ N, e|a y e|b, entonces e|d. 3. Se escribe d = m c d (a, b). Esto es lo mismo que decir que el m´aximo com´ un divisor de dos n´ umeros es el mayor de sus divisores comunes. Lo calculamos tomando, en la descomposici´on en factores primos de ambos, los factores primos comunes a a y b elevados a los menores exponentes. M´ınimo com´ un m´ ultiplo Definici´ on.-El m´ınimo com´ un m´ ultiplo de dos n´ umeros naturales a y b es otro n´ umero natural M tal que: 1. a|M y b|M. 2. Si p ∈ N, a|p y b|p, entonces M|p. 3. Se escribe M = m c m (a, b). Esto es lo mismo que decir que el m´ınimo com´ un m´ ultiplo de dos n´ umeros es el menor de sus m´ ultiplos comunes. Se calcula tomando, en la descomposici´on en factores primos de ambos n´ umeros, los factores primos comunes y no comunes elevados a los mayores exponentes.

Antonio Aranda, Jos´e M Chac´ on, Antonio Pozo

1

ESTALMAT-Andaluc´ıa Sesi´on: 19

Fecha: 14/04/07

T´ıtulo: Aritm´etica modular

Actividades 06/07 Segundo Curso

Actividad 1.– 1. Descomponer en producto de factores primos los n´ umeros a = 36 y b = 48. 2. Hallar el m c d (a, b) y el m c m (a, b). 3. Si llamamos d = m c d (a, b) y M = m c m (a, b), comprueba que se verifica la igualdad a·b =d·M (El producto de dos n´ umeros coincide con el producto de su m c d por su m c m). 4. Intenta demostrar esta propiedad para cualesquiera n´ umeros a y b naturales.

Algoritmo de Euclides Este algoritmo sirve para hallar el m c d de dos n´ umeros y se basa en los siguientes hechos: 1. Si r es el resto de la divisi´on de a entre b, entonces m c d (a, b) = m c d (b, r). 2. Si a es m´ ultiplo de b, entonces m c d (a, b) = b. 3. Se dividen los dos n´ umeros iniciales colocando el cociente encima del divisor y el resto debajo del dividendo. Luego el resto pasa a hacer el papel de divisor. Y as´ı, repitiendo la divisi´on, llegamos necesariamente a un resto 0. Entonces, el u ´ ltimo resto distinto de 0 es el m´aximo com´ un divisor buscado. Ejemplo: En la pr´actica hacemos el siguiente esquema, que aplicamos aqu´ı para el caso concreto de hallar el m´aximo com´ un divisor de 32 y 20

1 1 1 2 32 20 12 8 4 12 8 4 0 Por tanto, m c d (32, 20) = 4 Actividad 2.– 1. ¿Por qu´e en el algoritmo anterior se llega necesariamente a un resto 0? 2. Aplicar el Algoritmo de Euclides a 33 y 10 para calcular su m´aximo com´ un divisor. 3. Repetir el algoritmo para 456 y 108.

Antonio Aranda, Jos´e M Chac´ on, Antonio Pozo

2

ESTALMAT-Andaluc´ıa Sesi´on: 19

Fecha: 14/04/07

T´ıtulo: Aritm´etica modular

Actividades 06/07 Segundo Curso

Identidad de B´ ezout Dados dos n´ umeros naturales a, b, sea d = m c d (a, b). Entonces existen n´ umeros enteros x, y tales que d = a·x + b·y El c´alculo de los enteros x, y que aparecen en la identidad de B´ezout se basa en el algoritmo de Euclides para hallar el m´aximo com´ un divisor de dos n´ umeros, debiendo tener presente que los enteros que se obtienen no son u ´ nicos. Ejemplo: Hacemos el caso particular a = 33 y b = 10. El m´aximo com´ un divisor de 33 y 10 es 1:

3 3 3 33 10 3 1 3 1 0 Entonces: 1 = 10 − 3·3 = 10 − 3·(33 − 3·10) = 10 − 3·33 + 9·10 = 10·10 + 33·(−3) esto es, 1 = 10·10 + 33·(−3) de donde x = 10 e y = −3. Actividad 3.– 1. Encontrar una soluci´on a la identidad de B´ezout para 456 y 108. 2. Aplicar el caso particular anterior para resolver el siguiente problema de medir el tiempo con relojes de arena: ¿qu´e puedes hacer para medir un per´ıodo de 1 minuto si tienes un reloj de 33 minutos y otro de 10 minutos?

Antonio Aranda, Jos´e M Chac´ on, Antonio Pozo

3

ESTALMAT-Andaluc´ıa Sesi´on: 19

Fecha: 14/04/07

T´ıtulo: Aritm´etica modular

Actividades 06/07 Segundo Curso

Congruencias Definici´ on.- Fijemos un entero positivo n y sean a, b ∈ Z. Se dice que a es congruente con b (m´odulo n) si a y b dan el mismo resto al dividirlos por n. Ejemplo: 82 ≡ 34 (mod 6) porque al dividir 82 entre 6 da resto 4 y al dividir 34 entre 6 da resto 4. Observa que la diferencia 82 − 34 = 48 es m´ ultiplo de 6.

Actividad 4.– Decir que a y b dan el mismo resto al dividirlos entre n es equivalente a decir que a − b es m´ ultiplo de n. En notaci´on simb´olica: a ≡ b (mod n) ⇔ a − b ∈ Zn (Zn representa el conjunto de los m´ ultiplos de n) Trata de demostrar esta equivalencia. Recuerda que hay que hacerlo en los dos sentidos.

Propiedades: 1.

a) Reflexiva a ≡ a (mod n), ∀a ∈ Z. b) Sim´etrica Si a ≡ b (mod n), entonces b ≡ a (mod n). c) Transitiva Si a ≡ b (mod n) y b ≡ c (mod n), entonces a ≡ c (mod n).

2. Si a ≡ a′ (mod n) y b ≡ b′ (mod n), entonces a + b ≡ a′ + b′ (mod n) y ab ≡ a′ b′ (mod n).

Actividad 5.– Las demostraciones de estas propiedades son muy sencillas. Intenta hacer alguna de ellas. Puedes utilizar el resultado de la Actividad 4.

Actividad 6.– Probar las siguientes afirmaciones. 1. Los n´ umeros pares son congruentes dos a dos, m´odulo 2. 2. Los n´ umeros impares son congruentes dos a dos, m´odulo 2. 3. Los m´ ultiplos de n son congruentes con 0, m´odulo n. 4. Todo n´ umero es congruente, m´odulo n, con el resto de su divisi´on por n.

Antonio Aranda, Jos´e M Chac´ on, Antonio Pozo

4

ESTALMAT-Andaluc´ıa Sesi´on: 19

Fecha: 14/04/07

T´ıtulo: Aritm´etica modular

Actividades 06/07 Segundo Curso

Criterios de divisibilidad Divisibilidad entre 3 Vamos a ver, utilizando congruencias, que un n´ umero es divisible entre 3 si la suma de sus cifras es divisible entre 3. Consideremos, por ejemplo, el n´ umero 7542. Sabemos que su representaci´on en base decimal es: 7542 = 2 · 100 + 4 · 101 + 5 · 102 + 7 · 103 Calculemos los restos, m´odulo 3, de las sucesivas potencias de 10 (restos potenciales): 100 101 102 103

≡1 ≡1 ≡1 ≡1

(mod (mod (mod (mod

3) 3) 3) 3)

Multiplicando la primera congruencia por 2, la segunda por 4, la tercera por 5 y la u ´ ltima por 7, resulta: 7542 ≡ 2 + 4 + 5 + 7 (mod 3) de donde 7542 ser´a divisible por 3, si 2 + 4 + 5 + 7 es divisible por 3. Como 2 + 4 + 5 + 7 = 18 es divisible por 3, entonces 7542 es divisible por 3. En general, si a = a0 · 100 + a1 · 101 + . . . + ak · 10k se tiene 100 ≡ 1 (mod 101 ≡ 1 (mod 102 ≡ 1 (mod ... k 10 ≡ 1 (mod

3) 3) 3) 3)

Por tanto, a ≡ a0 + a1 + . . . + ak (mod 3), de donde: Un n´ umero es divisible por tres si la suma de sus cifras es divisible por tres. Actividad 7.– Halla, utilizando congruencias, los criterios de divisibilidad para: 9, 2, 5, 11 y 7.

Antonio Aranda, Jos´e M Chac´ on, Antonio Pozo

5

ESTALMAT-Andaluc´ıa Sesi´on: 19

Fecha: 14/04/07

T´ıtulo: Aritm´etica modular

Actividades 06/07 Segundo Curso

Actividad 8.– Un enigma: emulando a Sherlock Holmes. La escena transcurre en Granada en junio de 2005. Hace poco he tenido que ir a renovarme el carnet de identidad, que llevaba ya un par de meses caducado. Es una de esas cosas que tiene uno que hacer tarde o temprano, as´ı que el otro d´ıa iba yo todo dispuesto a plantar all´ı la huella de mi pulgar y marcharme, hasta que me encontr´e en la comisar´ıa con una cola de unas quince personas, todas ellas esperando a renovar su carnet o hacerse el pasaporte. Una verdadera pesadez. En fin, paciencia. Delante de m´ı iba una mujer con un bolso naranja que aparentemente se aburr´ıa tanto o m´as que yo, as´ı que empezamos a quejarnos por pasar el rato: – Yo no s´e por qu´e no pueden poner a m´as gente, si ven que ahora, antes de las vacaciones, todo el mundo quiere renovarse el carnet. Hacernos esperar aqu´ı, con este calor ..., dec´ıa ella. – Desde luego, desde luego, contest´e, porque yo me tengo que ir y pod´ıan darse un poco de prisa. Claro que hay que entenderlos, todo el d´ıa rellenando lo mismo ... – Dije eso porque tampoco me gusta meterles mucha prisa a los pobres. – Pues por eso mismo. Si llevan todo el d´ıa as´ı, pod´ıan tener ya un poco m´as de pr´actica, ¿no? Que yo me tengo que ir esta tarde a Chiclana con mi hermana y todav´ıa no tengo ni las maletas hechas, ¿sabes? – Al decirlo, me fij´e en que ten´ıa acento de C´adiz y le pregunt´e por eso. – ¡S´ı, en mi familia somos todos de C´adiz! Yo estuve all´ı hasta los catorce a˜ nos y luego me vine a Granada, y mi hermana se fue a M´alaga. Desde entonces alternamos las visitas cada tres a˜ nos: uno me voy yo a M´alaga, otro la invito yo aqu´ı a mi casa, y el tercero nos vamos las dos a Chiclana a ver a mis padres. Hemos hecho eso desde que nos fuimos de C´adiz; recuerdo el verano que pasamos con mis padres cuando yo ten´ıa diecisiete a˜ nos ... Me encanta esa playa ... – En ese momento pareci´o acordarse de la cola, y dijo – ¡A ver si terminan ya y puedo irme de una vez! S´olo quedaban tres personas delante de nosotros; tres o cuatro minutos m´as. – ¿Sabes? Cuando ten´ıa dieciocho a˜ nos me hice el carnet de identidad. Desde entonces lo he renovado puntualmente cada cinco a˜ nos, como debe ser, y nunca he tenido que esperar tanto. Hoy todo el mundo se ha puesto de acuerdo para venir ¿eh? – S´ı, eso parece. Estuvimos esperando un poco m´as y cuando s´olo quedaba una persona delante de nosotros nos dieron el impreso para poner nuestros datos (’rellenen esto, y firmen aqu´ı, aqu´ı y aqu´ı’).. Mientras escrib´ıamos, vi casualmente que la mujer con la que hab´ıa estado hablando se llamaba Amparo y que hab´ıa nacido un 29 de febrero. ’Vaya, curioso d´ıa’, pens´e. Terminamos, entregamos los impresos y las fotos, pusimos la huella donde correspond´ıa y nos limpiamos con la toallita que nos dieron. Le dije a la mujer que hasta luego, le dese´e que se lo pasara bien en la playa con su hermana y me qued´e pensando mientras me iba a casa que, verdaderamente, Amparo parec´ıa mucho m´as joven de lo que en realidad era. ¿Cu´ antos a˜ nos ten´ıa Amparo? Intenta resolver l´ogicamente el enigma. Antonio Aranda, Jos´e M Chac´ on, Antonio Pozo

6

ESTALMAT-Andaluc´ıa Sesi´on: 19

Fecha: 14/04/07

T´ıtulo: Aritm´etica modular

Actividades 06/07 Segundo Curso

Actividad 9.– Comprueba que la soluci´on del enigma se halla resolviendo el siguiente sistema de ecuaciones “modulares”, donde x es la edad de Amparo: x ≡ 17 (mod 3) x ≡ 18 (mod 5) 2005 − x ≡ 0 (mod 4) o, equivalentemente,

Vamos a ver c´omo se resuelve:

  x ≡ 2 (mod 3) (S) x ≡ 3 (mod 5)  x ≡ 1 (mod 4)

1. Intenta resolver primero el siguiente sistema   a (S1 ) a  a

modular: ≡ 1 (mod 3) ≡ 0 (mod 5) ≡ 0 (mod 4)

´ n.- Como m.c.d. (3, 20) = 1, por la identidad de B´ezout, tenemos que 7·3 − 1·20 = 1. Solucio Esto es, −20 = 3·(−7) + 1, lo que nos dice que −20 (que da resto 0 al dividirlo entre 20) da resto 1 al dividirlo entre 3. As´ı, tenemos una soluci´on:   −20 ≡ 1 (mod 3) −20 ≡ 0 (mod 5)  −20 ≡ 0 (mod 4)

2. Haz lo mismo con:

  b ≡ 0 (mod 3) (S2 ) b ≡ 1 (mod 5)  b ≡ 0 (mod 4)

Indicaci´on: Utiliza B´ezout con 5 y 12. 3. Haz lo mismo con:

  c ≡ 0 (mod 3) (S3 ) c ≡ 0 (mod 5)  c ≡ 1 (mod 4)

Indicaci´on: Utiliza B´ezout con 4 y 15.

4. Comprueba que x = 2a + 3b + c = −127 es una soluci´on del sistema (S). 5. Demuestra que, sumando m´ ultiplos enteros de 60 = 3·5·4, se obtienen otras soluciones, entre ellas las del enigma inicial.

Antonio Aranda, Jos´e M Chac´ on, Antonio Pozo

7