Criterios de divisibilidad y Congruencias Rafael F. Isaacs G.

*

Fecha: 9 de marzo de 2007 Cuando tenemos un n´ umero muy grande escrito en base 10 y deseamos saber si es m´ ultiplo por ejemplo de 9 no necesitamos hacer la divisi´on, simplemente sumamos sus cifras y si el resultado es m´ ultiplo de 9 el n´ umero original es m´ ultiplo de 9. Este es un t´ıpico criterio de divisibilidad, que se utiliza desde la escuela primaria. Uno m´as sencillo es para saber si un n´ umero es par: se mira la u ´ltima cifra y si ella es par todo el n´ umero es par. La justificaci´on de estos criterios radica en el sistema de numeraci´on que se utiliza y la demostraci´on de su validez, que haremos aqu´ı bas´andonos el la teor´ıa de congruencias, nos proporciona elementos para formular nuevos criterios de divisibilidad. El siguiente lema, que es consecuencia inmediata de la definici´on de congruencia, es la raz´on por la que utilizaremos esta teor´ıa para lograr nuestros objetivos. Lema 1. Un n´ umero k es divisible por c si y solo si k ≡ 0

(m´od c)

Demostraci´ on. (obvio). Para la lectura de este cap´ıtulo adem´as de manejar las congruencias el lector debe estar familiarizado con los sistemas de numeraci´on posicionales. Se aplica especialmente el Teorema fundamental de la numeraci´on.

1.

Criterios de la u ´ ltima cifra

Algunas veces para ver si un n´ umero es divisible por otro es suficiente con observar la u ´ltima cifra. Esto depende realmente de que el divisor divida la base, como cuando se trabaja en base 10 y se quiere saber si un entero es divisible por 2 o por 5. Proposici´ on. Sea a = (an an−1 . . . a1 a0 )b si b ≡ 0 (m´od c) entonces a es divisible por c si y solo si a0 ≡ 0 (m´od c) Demostraci´ on. Sabemos que a = a0 + a1 b + a2 b2 + ... + an bn−1 y como b ≡ 0 (m´od c), aplicando aritm´etica de congruencias se obtiene que a ≡ a0 (m´od c), que en combinaci´on con el lema 1 nos proporciona el resultado deseado. *

Este texto es un cap´ıtulo actualizado de las notas de clase del autor tituladas “N´ umeros enteros, teor´ıa, algoritmos y divertimentos´´ UIS, 1990

1

N´otese que lo que se demuestra es que, en este caso, la u ´ltima cifra (a0 ) determina la clase de congruencia m´odulo c, a la cual pertenece el entero a. Es decir, lo que se obtiene observando la u ´ltima cifra, es el residuo al dividir por c Ejemplo 1. Un n´ umero escrito en base 12 es divisible por 4 si termina en 0, 4 u 8, pues estos son los tres d´ıgitos de la base 12 que se dejan dividir por 4. Ejemplo 2. Como ya se dijo una aplicaci´on de la proposici´on 1 a la base decimal, encontramos los conocidos criterios para saber cu´ando un entero es divisible por 2 o por 5. Sin embargo estos criterios no sirven cuando el n´ umero es escrito en cualquier base. Para base 15 el criterio del 2 no es v´alido aunque el del 5 casi. Por qu´e?

2.

Criterios de la suma de las cifras.

Otras veces la suma de las cifras indica si se es o no divisible por otro. Es el caso de los conocidos criterios para saber si un n´ umero es divisible por 3 o por 9, cuando est´a escrito en nuestra base decimal. La siguiente proposici´on justifica estos y otros casos. ’ Proposici´ on. Sea a = (an an−1 . . . a1 a0 )b si b ≡ 1 (m´od c) entonces a es divisible por c si y solo si a0 + a1 + a2 + . . . + an ≡ 0 (m´od c) Demostraci´ on. Sabemos que a = a0 + a1 b + a2 b2 + ... + an bn−1 y como b ≡ 1

(m´od c), aplicando aritm´etica de congruencias se obtiene que a0 ≡ a0 a1 b ≡ a1 .. .

(m´od c) (m´od c)

an b n ≡ an

(m´od c)

entonces sumando estas congruencias tenemos a a ≡ a0 + a1 + a2 + ... + an

(m´od c)

que en combinaci´on con el lema 1 nos proporciona el resultado deseado. Presentamos las aplicaciones de esta proposici´on como corolarios: Corolario. Si b es congruente con 1 m´odulo c y el n´ umero a est´ a escrito en base b, entonces a es congruente con la suma de sus cifras m´odulo c. Corolario. Si b es congruente con 1 m´odulo c, entonces para saber si un n´ umero (escrito en base b) es divisible por c es suficiente saber si la suma de sus cifras lo es. Ejemplo 3. (Base decimal) La suma de las cifras del entero 19168639 es 43 por tanto: 19168639 ≡ 1 (m´od 3); 19168639 ≡ 7 (m´od 9) Ejemplo 4. En base 4, la suma de las cifras del entero a es congruente con a m´odulo 3 pero no m´odulo 9. 2

3.

Criterios de la suma y resta de las cifras Empecemos mostrando un ejemplo:

Ejemplo 5. Para saber si un n´ umero escrito en base decimal es divisible por 11, se halla la diferencia entre la suma de cifras de lugares pares y la suma de las cifras de lugares impares; el n´ umero es m´ ultiplo de 11 , si y solo si, esta diferencia lo es. Digamos, para saber si 19168639 es divisible por 11, sumamos las cifras de lugares impares: 9+6+6+9=30 ; sumamos las cifras de lugares pares: 3+8+1 +1=13; hacemos la diferencia de estas dos sumas: 30-13=17. Como 17 no es m´ ultiplo de 11 entonces 19168639 no es m´ ultiplo de 11. Es m´as, como se ve en la demostraci´on de la siguiente proposici´on se tiene que 17 ≡ 19168639 (m´od 11). N´otese que si a = (an , an−1 , ..., a1 , a0 )b la diferencia entre la suma de cifras de lugares pares y la suma de las cifras de lugares impares viene dada por la expresi´on: a0 − a1 + a2 − ... + (−1)n an Proposici´ on. Sea a = (an , an−1 , ..., a1 , a0 )b si b ≡ −1

(m´od c) entonces

a ≡ a0 − a1 + a2 − ... + (−1)n an

(m´od c)

Demostraci´ on. Ejercicio (es similar a la demostraci´on de la proposici´on 2). Corolario. Sea a = (an , an−1 , ..., a1 , a0 )b si b ≡ −1 (m´od c) entonces a es divisible por c si y solo si a0 − a1 + a2 − ... + (−1)n an ≡ 0 (m´od c) Corolario. Si b es congruente con −1 m´odulo c, entonces para saber si un n´ umero (escrito en base b) es divisible por c es suficiente saber si la suma de cifras de lugares pares menos la suma de las cifras de lugares impares es m´ ultiplo de c.

4.

Criterios con bloques de cifras

Algunas veces es conveniente considerar las cifras de un n´ umero tomadas de dos en dos, o de tres en tres (siempre de derecha a izquierda). Aqu´ı realmente, se est´a pasando el n´ umero a 2 3 base b o b , como se resalta en el siguiente lema cuyo enunciado y demostraci´on se dej´o como ejercicio en secci´on anterior. Lema 2. Las cifras de a escrito en base bm son las mismas que en base b pero tomadas de derecha a izquierda en bloques de m: Cada grupo de m cifras en base b corresponde a un d´ıgito en base bm Ejemplo 6. Para pasar de base 2 a base 8 el entero (10010101110001110)2 traducimos los bloque de 3 as´ı: (110)2 = 6;

(001)2 = 1;

(110)2 = 6;

(101)2 = 5;

(010)2 = 2;

(10)2 = 2;

entonces las cifras en base 8 son 6, 1, 6, 5, 2, 2 (tomadas de derecha a izquierda) es decir: (10010101110001110)2 = (225616)8 . 3

Si quisi´eramos pasar a base 16 escoger´ıamos grupos de a 4 y tendr´ıamos: (1110)2 = E;

(1000)2 = 8;

(1011)2 = B;

(0010)2 = 2;

(1)2 = 1

y tenemos: (10010101110001110)2 = (12B8E)16 . Cuando la base es muy grande podr´ıamos agotar las letras del alfabeto, entonces no se acostumbra colocar nuevas letras, sino dejar los d´ıgitos decimales. Por ejemplo para pasar de base decimal a base 100, se necesitar´ıa agregar 90 nuevos d´ıgitos, mejor entender las parejas de d´ıgitos decimales como d´ıgitos centesimales, as´ı: (19168639)10 = (19 : 16 : 86 : 39)100 1 Al aplicar el lema 2 con alguna de las proposiciones 1, 2 o 3, para alg´ un m podremos ’ conseguir y explicar otros criterios de divisibilidad, como se muestra en los siguientes ejemplos: Ejemplo 7. (Base decimal) Para saber si un entero es m´ ultiplo de 100, todos sabemos que basta con saber si sus dos u ´ltimas cifras son exactamente 00. ¡Claro! Cuando escribimos los n´ umeros en base 100 los m´ ultiplos de 100 son los que terminan en cero, pero este d´ıgito se representa con dos ceros de la base decimal. Por otra parte, aplicando la proposici´on 1 al lema 2 obtenemos que por ejemplo, cualquier entero es congruente modulo 25 con sus dos u ´ltimas cifras ya que 25 divide a 100. Otra manera de saber si un n´ umero escrito en base 10 es divisible por 11 es hacer la suma de sus cifras tomadas de dos en dos. Por ejemplo: 19168639 ≡ 19 + 16 + 86 + 39 = 160 ≡ 60 + 1 ≡ 6

(m´od 11)

¡Compare con el ejemplo 5! Ejemplo 8. Busquemos un criterio para saber si un entero escrito en base 2 es m´ ultiplo de 3. Como 4 ≡ 1 (m´od 3) entonces en base 4 se puede aplicar la proposici´on 2 y tenemos que un n´ umero escrito en base 4 es congruente m´odulo 3 con la suma de sus cifras (ejemplo 4) pero seg´ un el lema 2 las cifras de base 4 son las parejas de cifras en base 2, entonces: “Un n´ umero escrito en base 2 es m´ ultiplo de 3 si y solo si la suma de sus cifras tomadas de dos es dos de derecha a izquierda es m´ ultiplo de 3”.

5.

Separando las u ´ ltimas cifras

El operador “quitar” la u ´ltima cifra, o las dos u ´ltimas, parece que no fuera un operador aritm´etico. Seg´ un el Teorema fundamental de la numeraci´on, y trabajando en base decimal, si la u ´ltima cifra de n es a, entonces n tendr´a la forma n = 10n′ + a con 0 < a < 10, en donde n′ es precisamente lo que “queda”. Si lo que se quita a n son las dos u ´ltimas cifras, entonces convendr´a considerar la forma de n como n = 100n′ + a en donde a es el valor de las dos u ´ltimas cifras (0 < a < 100) y n′ es “lo que queda”. Utilizando este sencillo operador, podemos encontrar u ´tiles criterios de divisibilidad, que se justifican por alguna ecuaci´on de congruencias. 1

En algunos idiomas, por ejemplo el ingl´es, se usa definitivamente la base cien: para decir 2019 el gringo dice “veinte, diez y nueve ”.

4

Ejemplo 9. Un n´ umero escrito en base 10 es divisible por 17, si y solo si, al quitar sus dos u ´ltimas cifras y restarlas del duplo de lo que queda, el resultado es m´ ultiplo de 17. Por ejemplo, para saber si 4767 es m´ ultiplo de 17: quito 67 y lo que queda es 47, su duplo 94, menos 67, obtengo 27, que no es m´ ultiplo de 17 por tanto 4767 tampoco lo es, pero si pruebo con 4267 tengo (42 × 2) − 67 = 84 − 67 = 17, y por tanto 4267 si es m´ ultiplo de 17. La demostraci´on de que este procedimiento es v´alido, parte de considerar n con la forma n = 100n′ + b , donde n′ es lo “que queda” y b es el n´ umero representado por las dos u ´ltimas ′ cifras; debemos ver que n ≡ 0 (m´od 17) si y solo si, 2n − b ≡ 0 (m´od 17) y esta es una equivalencia de congruencias, que se demuestra f´acilmente: n = 100n′ + b 15n′ + b −2n′ + b 2n′ − b

6.

≡ ≡ ≡ ≡

0 0 0 0

(m´od (m´od (m´od (m´od

17) 17) 17) 17)

PREGUNTAS Y EJERCICIOS. Demostrar los siguientes criterios de divisibilidad:

1. En base diez un n´ umero es divisible por 2, si termina en cifra par. 2. En base diez un n´ umero es divisible por 5, si termina en 0 o 5. 3. En base diez un n´ umero es divisible por 20, si termina en 00, 20, 40, 60 ´o 80. 4. En base 12 un n´ umero es divisible por 3, si su u ´ltima cifra lo es. 5. En base 12 un n´ umero es divisible por 6, si termina en 0 ´o 6. 6. En base 2 los m´ ultiplos de 4 son aquellos que terminan en 00. 7. En base diez un n´ umero es divisible por 9, si la suma de sus cifras es divisible por 9. 8. En base 6 un n´ umero es divisible por 5, si la suma de sus cifras es divisible por 5. 9. En base diez un n´ umero es divisible por 37, si la suma de sus cifras tomadas de tres en tres, es divisible por 37. 10. En base 4 un n´ umero es divisible por 15, si la suma de sus cifras, tomadas de os en dos, es divisible por 15. 11. Si a un n´ umero que est´a escrito en base 10 y es m´ ultiplo de 13, se le quita su u ´ltima cifra y se le suma multiplicada por 4 a lo que queda, el resultado es m´ ultiplo de 13. 12. Si a un n´ umero que est´a escrito en base 10 y es m´ ultiplo de 11, se le quita su u ´ltima cifra y se le suma a lo que queda, el resultado es m´ ultiplo de 11. 13. Enuncie y demuestre un criterio para saber si un n´ umero escrito en base decimal es divisible por 19.

5