Blogia
Tio Petros

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 -

0 [menor_o_igual] r [menor] valor_absoluto(b)

Isaac -

0 [menor_o_igual] r [menor] b

Isaac -

Tercer intento.
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 -

Parece que me ha cortado el envío anterior. Debería imponerse 0

Isaac -

Supongo que será una simple errata, pero si no imponemos a>=0 y b>0 habrá que hacer
0

jose -

juer, sí que se nota el cambio de estilo :-O