1

SESIONES 2.4

ARITMÉTICA MODULAR

En algunas situaciones sólo interesan los restos de las divisiones por enteros. Por ejemplo, cuando preguntamos qué hora será (en un reloj de 24 horas) dentro de cincuenta horas, nos interesa sólo el resto de la división de 50 más la hora actual entre 24.

Como es frecuente que sólo nos interesen los restos de las divisiones, tenemos notaciones especiales para ellos.

Existe una notación para indicar que dos enteros tienen el mismo resto cuando se dividen por el entero positivo m.

Definición 8 Si a y b son enteros y m es un entero positivo, entonces a es congruente a b modulo m, si m

divide a-b. Se usa la notación a≡b(mod m) para indicar que a es congruente a b modulo m.

Se usa la notación a≡b(mod m) para indicar que a no es congruente a b modulo m.

Teorema 8

Sean a y b enteros y sea m un entero positivo. Entonces a≡b(mod m) si y solo si:

a mod m=b mod m. Ex16a. ¿Es 17 congruente a 5 modulo 6?

17-5=12 y 6≡12. Luego 17≡5 (mod 6).

Ex16b. ¿Es 24 congruente a 14 modulo 6?

Teorema 9 Sea m un entero positivo. Los enteros a y b son congruentes modulo m si y solo si hay un

entero k tal que a=b+km.

Ex. Si a=22 y m=5, determine valores de k y b tal que a=b+km Sol. 22=(17)+(1)5 =(12)+(2)5 =(7)+(3)5 =(2)+(4)5 =(-3)+(5)5 =(-8)+(6)5.

Luego 22≡17(mod 5), 22≡12(mod 5), 22≡7(mod 5), 22≡-3(mod 5), 22≡-8(mod 5)

El conjunto de todos los enteros congruentes a un entero a modulo m es llamado la clase de congruencia de a modulo m.

2

Teorema 10

Sea m un entero positivo. Si a≡b(mod m) y c≡d(mod m), entonces a+c≡b+d(mod m) y

ac≡bd(mod m)

Ex17. Puesto que 7≡2(mod 5) y 11≡1(mod 5) del teorema anterior se tiene que

18 = 7+11 ≡ 2 + 1 = 3 (mod 5) y

77 = 7 11 ≡ 2 1 = 2 (mod 5)