Aritmética modular (3)
Tercer post de Lola Cárdenas sobre reglas de divisivilidad
_________________________________________________________
Aritmética modular
¿Y todo esto qué tiene que ver con las reglas de divisibilidad? Eso es lo que vamos a ver ahora. En realidad, los conceptos preliminares que hemos visto sirven para mucho más, pero en este caso los vamos a aplicar a nuestro objeto de estudio.
Asumimos que vamos a trabajar con el conjunto de los números enteros,
, dotado de las operaciones usuales de suma ( 
) y producto ( 
). Vamos a definir una relación binaria de equivalencia en 
y a continuación ver qué tiene que ver con lo que pretendemos llevar adelante: las reglas de divisibilidad.Congruencias
Definición de la relación de equivalencia de la congruencia
Sea
un entero positivo. Decimos que dos números enteros 
, 
son congruentes módulo si existe un número 
tal que 
. Para denotar esta situación, se utiliza la notación: 
. Vamos a comprobar que la relación de congruencia módulo m es una relación binaria de equivalencia. Es muy sencillo, y lo hacemos a modo de ilustrar un poco más el procedimiento.Comenzaremos probando la propiedad reflexiva. Dado
, ¿se cumplirá que 
? Es decir, ¿tendremos que existirá un tal que 
? Como 
, es evidente que si escogemos 
, se cumple entonces que . Luego este existe, y por tanto hemos verificado la propiedad reflexiva.Veamos la propiedad simétrica. Dados
, supongamos que 
. ¿Se cumplirá que 
? Esto será así si existe un tal que 
. Ahora bien, sabemos por hipótesis que 
luego, por definición de la relación, se verifica que existe un tal que . Como 
, tenemos entonces que 
. Tomamos pues el entero 
(si , también ), y por tanto se verifica la propiedad simétrica.Queda por último la transitiva. Dados
tales que y 
, ¿será cierto que 
? Esto será así si existe un tal que 
.Como
, sabemos que existe un 
tal que 
. Igualmente, como , sabemos que existe un 
tal que 
.Vamos a ver en qué queda entonces
:
Luego si tomamos
, es claro pues que se verifica la propiedad transitiva, y ya tenemos probada la condición de equivalencia de la relación binaria definida.Clases de equivalencia módulo m
Una vez definida esta relación binaria de equivalencia, y probado que, efectivamente, lo es, vamos a dar el siguiente paso, que será delimitar las clases de equivalencia resultado de partir el conjunto de los números enteros de acuerdo a esta relación.
Tenemos que la congruencia módulo m divide al conjunto
en m clases de equivalencia, 
, 
, 
, ..., 
. La clase de equivalencia del cero serán todos aquellos números múltiplos de m. La clase de equivalencia del uno serán todos aquellos números tales que al dividir por m, nos dan de resto 1. La clase de equivalencia del dos serán todos aquellos números tales que al dividir por m, nos dan de resto 2. Y así hasta el 
.Veamos algunas para aclararlo:
Efectivamente, la clase de equivalencia del cero son todos los múltiplos enteros de m. Veamos la clase de equivalencia del 1:
Por el algoritmo de la división, vemos que k es el cociente de dividir a por m, y 1 el resto de dicha división. Luego, como decíamos arriba, la clase de equivalencia del 1 son todos aquellos números enteros tales que al dividir por m, dan de resto 1.
Igualmente tendríamos con la clase de equivalencia del 2:
Y así, hasta
:
¿Por qué paramos en
? ¿Qué sucede con la clase de equivalencia del m? Si escribimos cuál sería, lo veremos claro:
Volvemos a la clase de equivalencia del cero. Igualmente, la clase de equivalencia de
coincide con la clase de equivalencia del 1. Y así, sucesivamente.Algoritmo de la división
Dados
, 
, existen dos números enteros c y r tales que 
, con 
. Los enteros c y r (cociente y resto, respectivamente) son únicos, dados a y b.
6 comentarios
Isaac -
Isaac -
Isaac -
0 <= r < b o nos exponemos a
(-5)= 3 * (-1) + (-2)
(-5)= 3 * (-2) + 1
que no es única, o incluso
5 = (-3) * (-1) + 2
5 = (-3) * (-2) + (-1)
donde no existe 0 <= r < (-3)
Isaac -
Isaac -
0
jose -